BFS与DFS

发表于   |   分类于   |  

BFS

为了实现各个状态按照其被查找到的顺序依次转移扩展，我们需要使用一个队列。即将每次扩展得到的新状态放入队列，待排在其之前的状态都被扩展完成后，该状态才能得到扩展。

BFS相当于层次遍历，一般求最优解用BFS.

题目描述：

Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.魔王住在一个城堡里,城堡是一个ABC的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1.

输入

输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它们分别代表城堡的大小和魔王回来的时间.然后是A块输入数据(先是第0块,然后是第1块,第2块……),每块输入数据有B行,每行有C个正整数,代表迷宫的布局,其中0代表路,1代表墙。

输出

对于每组测试数据,如果Ignatius能够在魔王回来前离开城堡,那么请输出他最少需要多少分钟,否则输出-1.

样例输入

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

样例输出

11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<stdio.h>
#include<queue>
using namespace std;
bool mark[55][55][55];
int maze[55][55][55];
struct  sta
{
    int x,y,z;
    int t;
};

queue<sta> Q;

int go[][3]={0,0,1,
                    0,0,-1,
                    0,1,0,
                    0,-1,0,
                    1,0,0,
                    -1,0,0};

int BFS(int a,int b,int c)
{
    while(Q.empty()==false)
    {
        sta now=Q.front();
        Q.pop();
        for(int i=0;i<6;i++)
        {
            int nx=now.x+go[i][0];
            int ny=now.y+go[i][1];
            int nz=now.z+go[i][2];
            int nt=now.t+1;
            if(nx<0||nx>=a||ny<0||ny>=b||nz<0||nz>=c) continue;
            if(mark[nx][ny][nz]==true) continue;
            if(maze[nx][ny][nz]==1) continue;
            if(nx==a-1&&ny==b-1&&nz==c-1)
                return nt;
            else
            {
                sta t;
                t.t=nt;
                t.x=nx;
                t.y=ny;
                t.z=nz;
                Q.push(t);
                mark[nx][ny][nz]=true;
            }
        }
    }
    return -1;
}

int main()
{
    int k;
    scanf("%d",&k);
    while(k--)
    {

    int a,b,c,T;
   scanf("%d%d%d%d",&a,&b,&c,&T);
        for(int i=0;i<a;i++)
        {
            for(int j=0;j<b;j++)
            {
                for(int k=0;k<c;k++)
                {
                    scanf("%d",&maze[i][j][k]);
                    mark[i][j][k]=false;
                }
            }
        }
        while(Q.empty()==false)
        {
            Q.pop();
        }
        sta start;
        start.x=0;
        start.y=0;
        start.z=0;
        start.t=0;
        Q.push(start);
        int result=BFS(a,b,c);
        if(result>T)
            printf("-1\n");
        else
            printf("%d\n",result);
    }
    return 0;
}

递归

描述

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

输入

The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either *', representing the absence of oil, or@’, representing an oil pocket.

输出

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

样例输入

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

样例输出

0
1
2
2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<stdio.h>
char maze[105][105];
bool mark[105][105];
int go[][2]={0,1,
                    0,-1,
                    1,0,
                    -1,0,
                    1,1,
                    1,-1,
                    -1,1,
                    -1,-1};
int a,b;
void DFS(int x,int y)
{
    for(int i=0;i<8;i++)
    {
            int nx=x+go[i][0];
            int ny=y+go[i][1];
            if(nx<0||nx>=a||ny<0||ny>=b) continue;
            if(maze[nx][ny]=='*') continue;
            if(mark[nx][ny]==true) continue;
            mark[nx][ny]=true;
            DFS(nx,ny);
    }
    return ;
}
int main()
{
    while(scanf("%d%d",&a,&b)!=EOF&&a!=0&&b!=0)
    {
        for(int i=0;i<a;i++)
        {
                scanf("%s",maze[i]);
        }
        for(int i=0;i<a;i++)
            for(int j=0;j<b;j++)
                mark[i][j]=false;

        int ans=0;
        for(int i=0;i<a;i++)
        {
            for(int j=0;j<b;j++)
            {
                if(maze[i][j]=='*') continue;
                if(mark[i][j]==true) continue;
                DFS(i,j);
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

DFS

由于DFS缺少了广度搜索中按层次递增顺序遍历的特性，所以当深度优先搜索搜索到我们需要的状态时，其不再具有某种最优的特性。因此，在使用DFS时，我们更多的是求解有或没有的问题，即对解答树是否有我们需要的结果进行判定，而一般不使用DFS求解最优解问题。

描述

The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.

输入

The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
‘X’: a block of wall, which the doggie cannot enter;
‘S’: the start point of the doggie;
‘D’: the Door; or
‘.’: an empty block.
The input is terminated with three 0’s. This test case is not to be processed.

输出

For each test case, print in one line “YES” if the doggie can survive, or “NO” otherwise.

样例输入

4 4 5
S.X.
..X.
..XD
….
3 4 5
S.X.
..X.
…D
0 0 0

样例输出

NO
YES

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<stdio.h>

int N,M,T;
char maze[10][10];
bool mark[10][10];
bool success; //这里设置一个状态符，如果DFS能达到要求，则设置为true,如果不能，则不改变。
struct sta
{
    int x;
    int y;
    int t;
};
int go[][2]={1,0,
                    -1,0,
                    0,1,
                    0,-1};

void DFS(sta start)
{
    if(maze[start.x][start.y]=='D'&&start.t==T)
     {
         success=true;
         return;
     }
    for(int i=0;i<4;i++)
    {
        int nx=start.x+go[i][0];
        int ny=start.y+go[i][1];
        int nt=start.t+1;
        if(nx<0||nx>=N||ny<0||ny>=M) continue;
        if(maze[nx][ny]=='X') continue;
        if(mark[nx][ny]==true) continue;
        sta next;
        next.x=nx;
        next.y=ny;
        next.t=nt;
        mark[nx][ny]=true;
        DFS(next);
        mark[nx][ny]=false;
    }
}
int main()
{
    while(scanf("%d%d%d",&N,&M,&T)!=EOF)
    {
        success=false;
        if(N==0&&M==0&&T==0)
            break;
        for(int i=0;i<N;i++)
        {
            scanf("%s",maze[i]);
        }
        sta start;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                if(maze[i][j]=='S')
                {
                    start.x=i;
                    start.y=j;
                    start.t=0;
                }
                if(maze[i][j]=='.')
                {
                    mark[i][j]=false;
                }
            }
        }
        DFS(start);
        if(success)
            printf("YES\n");
        else
            printf("NO\n");
    }
}