迷宫

一、心得

这个题目最主要的问题是DFS还是回溯的选取：这题用DFS

DFS和回溯的区别
DFS就是找一个解，回溯是找所有解
DFS也会遍历掉所有的格子，回溯是多次遍历所有的格子

二、题目及分析

1792:迷宫

总时间限制:: 3000ms
内存限制:: 65536kB

描述

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。

输入

第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。

输出

k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。

样例输入

2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0

样例输出

YES
NO

三、AC代码

1、

 1 //1792:迷宫
 2 /*
 3 DFS和回溯的区别
 4 DFS就是找一个解，回溯是找所有解
 5 DFS也会遍历掉所有的格子，回溯是多次遍历所有的格子
 6 */
 7 #include <iostream>
 8 #include <cstring>
 9 using namespace std;
10 //右下左上 
11 int hang[4]={0,1,0,-1};
12 int lie[4]={1,0,-1,0}; 
13 int vis[105][105];
14 char a[105][105];
15 int k,n;
16 int ha,la,hb,lb;
17 int ok;
18 bool search(int h,int l){
19     //cout<<h<<":"<<l<<endl;
20     if(h==hb&&l==lb) ok=1;
21     if(ok) return true;
22     else{
23         for(int i=0;i<4;i++){
24             int h1=h+hang[i];
25             int l1=l+lie[i];
26             if(h1>=0&&h1<n&&l1>=0&&l1<n&&a[h1][l1]=='.'&&!vis[h1][l1]){
27                 vis[h1][l1]=1;
28                 search(h1,l1);
29                 if(ok) return true;
30                 
31             }
32         } 
33         return false;
34     }
35 }
36 int main(){
37     //freopen("in.txt","r",stdin);
38     cin>>k;
39     while(k--){
40         cin>>n;
41         ok=0;
42         for(int i=0;i<n;i++){//i是行，j是列 
43             for(int j=0;j<n;j++){
44                 cin>>a[i][j];
45                 vis[i][j]=0;
46             }
47         }
48         cin>>ha>>la>>hb>>lb;
49         if(a[ha][la]=='#'||a[hb][lb]=='#'){
50             cout<<"NO"<<endl;
51             continue;
52         } 
53         else if((ha==hb)&&(la==lb)){
54             cout<<"YES"<<endl;
55             continue;
56         }
57         else{
58             vis[ha][la]=1;
59             int ok1=search(ha,la);
60             if(ok1) cout<<"YES"<<endl;
61             else cout<<"NO"<<endl;
62         }
63     }
64     return 0;
65 }

2、

 1 #include<iostream>
 2 #include <cstring>
 3 using namespace std;
 4 int u[4]={1,0,-1,0};//x四个转向 
 5 int v[4]={0,1,0,-1};//y四个转向 
 6 char a[101][101];
 7 bool b[101][101]={0};//记录是否走过 
 8 int ha,la,hb,lb,m,t;
 9 int ok=0;
10 void search(int i,int j)
11 {
12     
13     if(i==hb&&j==lb) ok=1;
14     if(ok) return;
15     int x,y,k;
16     for(int k=0;k<=3;k++)
17     {
18         if(ok) return;
19         x=i+u[k];
20         y=j+v[k];
21         if(x>=0&&x<t&&y>=0&&y<t&&(!b[x][y])&&(a[x][y]=='.')) 
22         {
23             if(ok) return;
24             //cout<<x<<":"<<y<<endl;
25             b[x][y]=1;
26             search(x,y);
27             if(ok) return;
28             //b[x][y]=0;
29             if(ok) return;
30         }
31     }
32     
33 }
34 int main()
35 {
36     //freopen("in.txt","r",stdin);
37     cin>>m;
38     while(m--)
39     {
40          memset(b,0,sizeof(b));
41          ok=0;
42          cin>>t;
43          for(int i=0;i<t;i++)
44          {
45              for(int j=0;j<t;j++)
46              {
47                  cin>>a[i][j];
48              }
49          }
50          cin>>ha>>la>>hb>>lb;
51          
52          if(a[ha][la]=='#'||a[hb][lb]=='#')
53          {
54              cout<<"NO"<<endl;
55              continue;
56          }
57          else if(ha==hb&&la==lb) cout<<"YES"<<endl;
58          else
59          {
60              b[ha][la]=1;
61              search(ha,la); 
62              if(b[hb][lb]) cout<<"YES"<<endl;
63              else cout<<"NO"<<endl;
64          }
65         
66     }
67     return 0;
68 }

3、

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 const int kx[4] = { 0, -1, 1, 0 }, ky[4] = { -1, 0, 0, 1 };
 7 int ka, kb;
 8 bool s[102][102] = { false };
 9 bool dfs(int x, int y) {
10     //cout<<x<<":"<<y<<endl;
11     cout<<x<<":"<<y<<endl;
12     if (ka == x && kb == y)
13         return true;
14     for (int i = 0; i < 4; i++)
15         if (s[x + kx[i]][y + ky[i]] == true) {
16             s[x + kx[i]][y + ky[i]] = false;
17             if (dfs(x + kx[i], y + ky[i]))
18                 return true;
19         }
20     return false;
21 }
22 int main() {
23     freopen("in.txt","r",stdin);
24     int ii, k, a, b, n, i, j;
25     char d;
26     scanf("%d", &k);
27     for (ii = 0; ii < k; ii++) {
28         scanf("%d", &n);
29         for (i = 1; i <= n; i++) {
30             getchar();
31             for (j = 1; j <= n; j++) {
32                 d = getchar();
33                 if (d == '.')
34                     s[i][j] = true;
35             }
36         }
37         scanf("%d %d %d %d", &a, &b, &ka, &kb);
38         a++;
39         b++;
40         ka++;
41         kb++;
42         if (s[ka][kb] == false || s[a][b] == false || !dfs(a, b))
43             printf("NO
");
44         else
45             printf("YES
");
46         for (i = 1; i <= n; i++)
47             for (j = 1; j <= n; j++)
48                 s[i][j] = false;
49     }
50     return 0;
51 }