DFS与BFS_1||dfs||dfs||h16100-0006||s01321a||862917371134-CSDN博客

DFS

Description
AveryBoy最近迷上了连连看游戏，于是他自己写了一个程序来玩，不过由于他学艺不精导致他写的连连看游戏连线不能从外面绕过。

游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。

Input
输入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000)
，分别表示棋盘的行数与列数。

在接下来的n行中，每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子，正整数表示棋子的类型。接下来的一行是一个正整数q(0<q<50)，表示下面有q次询问。在接下来的q行里，每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n=0,m=0时，输入结束。

Output
每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。

Sample Input
3 4
1 2 3 4
0 0 0 0
4 3 2 1
4
1 1 3 4
1 1 2 4
1 1 3 3
2 1 2 4
3 4
0 1 4 3
0 2 4 1
0 0 0 0
2
1 1 2 4
1 3 2 3
0 0

Sample Output
YES
NO
NO
NO
NO
YES

#include <bits/stdc++.h>
using namespace std;

int n,m,q;
const int maxn = 1010;
int che[maxn][maxn];
bool vis[maxn][maxn];
int sx,sy,ex,ey;
bool flag;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

void dfs(int x,int y,int dir,int turn)
{
    if(turn>2||flag) return;
    if(turn == 2&&(x-ex)!=0&&(y-ey)!=0) return;
    if(x==ex&&y==ey&&turn<=2){
        flag = 1;
        return;
    }

    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy]) continue;
        if(che[xx][yy]==0||(xx==ex&&yy==ey))
        {
            vis[xx][yy]=1;
            if(dir == i||dir==-1)
                dfs(xx,yy,i,turn);
            else
                dfs(xx,yy,i,turn+1);
            vis[xx][yy]=0;
        }
    }
    return;
}


int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)  break;
        memset(che,0,sizeof(che));

        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&che[i][j]);

        scanf("%d",&q);
        for(int i=0;i<q;i++)
        {
            scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
            memset(vis,0,sizeof(vis));

            flag = 0;
            if(che[sx][sy] == che[ex][ey]&&che[sx][sy])
            {
                vis[sx][sy] = 1;
                dfs(sx,sy,-1,0);
            }
            if(flag) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

BFS

Description
这次AveryBoy被困在一个三维迷宫中，他必须想办法在T分钟内离开迷宫（包括T）。迷宫是一个ABC的立方体，起点在（0，0，0）位置，终点在（A-1，B-1，C-1）位置。如果他能离开迷宫，输出离开迷宫所需最短时间，否则输出-1。

题目描述

Input
输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它们分别代表迷宫的大小和离开的时间.然后是A块输入数据(先是第0块,然后是第1块,第2块…),每块输入数据有B行,每行有C个正整数,代表迷宫的布局,其中0代表路,1代表墙.
Output
对于每组测试数据,如果AveryBoy能离开迷宫,那么请输出他最少需要多少分钟,否则输出-1.
Sample Input
1
3 3 4 20
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1
1 0 0 1
0 1 1 1
0 0 0 0
0 1 1 0
0 1 1 0
Sample Output
11

#include <bits/stdc++.h>
using namespace std;

int K,A,B,C,T;
int g[50][50][50];
bool vis[50][50][50];
int flag;

int dx[]={0,0,0,0,-1,1};
int dy[]={-1,1,0,0,0,0};
int dz[]={0,0,-1,1,0,0};


struct node
{
    int x,y,z,t;
};

bool can_move(int x,int y,int z)
{
    return 0<x&&x<=A&&0<y&&y<=B&&0<z&&z<=C&&!g[x][y][z]&&!vis[x][y][z];
}
void bfs(node start)
{

    queue<node> q;
    q.push(start);
    while(!q.empty())
    {
        node now = q.front();
        int nowx = now.x;
        int nowy = now.y;
        int nowz = now.z;
        int nowt = now.t;
        q.pop();

        if(nowt>T)
        {
            printf("-1\n");
            return;
        }

        if(nowx==A&&nowy==B&&nowz==C)
        {
            printf("%d\n",nowt);
            return;
        }

        for(int i=0;i<6;i++)
        {
            int newx = nowx + dx[i];
            int newy = nowy + dy[i];
            int newz = nowz + dz[i];
            if(can_move(newx,newy,newz))
            {
                vis[newx][newy][newz] = 1;
                node newnode;
                newnode.t = nowt + 1;
                newnode.x = newx;
                newnode.y = newy;
                newnode.z = newz;
                q.push(newnode);
            }
        }
    }

}
int main()
{
    scanf("%d",&K);
    while(K--)
    {
        flag = 0;
        memset(g,0,sizeof(g));
        memset(vis,0,sizeof(vis));
        scanf("%d%d%d%d",&A,&B,&C,&T);
        for(int i=1;i<=A;i++)
            for(int j=1;j<=B;j++)
                for(int k=1;k<=C;k++)
                    scanf("%d",&g[i][j][k]);
        vis[1][1][1] = 1;
        node start;
        start.x=1;
        start.y=1;
        start.z=1;
        start.t=0;
        bfs(start);
    }
}