1033. Labyrinth(dfs)

简单ｄｆｓ　有一点小小的坑　就是图可能不连通　所以要从左上和右下都搜一下　加起来　从讨论里看到的

讨论里看到一句好无奈的回复　“可不可以用中文呀。。。”

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 using namespace std;
 8 char s[40][40];
 9 int dis[4][2] = {0,1,1,0,-1,0,0,-1};
10 int vis[40][40],n,num;
11 int judge(int x,int y)
12 {
13     if(x<1||y<1||x>n||y>n)
14     return 0;
15     return 1;
16 }
17 void dfs(int x,int y)
18 {
19     int i;
20     for(i = 0 ; i < 4 ; i++)
21     {
22         int tx = dis[i][0]+x;
23         int ty = dis[i][1]+y;
24         if(judge(tx,ty)&&!vis[tx][ty])
25         {
26             if(s[tx][ty]=='#')
27             {
28                 num++;
29                 continue;
30             }
31             vis[tx][ty] = 1;
32             if(tx==n&&ty==n)
33             {
34                 dfs(tx,ty);
35                 continue;
36             }
37             if(tx==1||ty==1||tx==n||ty==n)
38                 num++;
39             if((tx==1&&ty==n)||(ty==1&&tx==n))
40                 num++;
41             dfs(tx,ty);
42         }
43     }
44 }
45 int main()
46 {
47     int i,j;
48     scanf("%d",&n);
49     for(i = 1; i <= n ; i++)
50         for(j = 1 ; j <= n ; j++)
51         cin>>s[i][j];
52     vis[1][1] = 1;
53     dfs(1,1);
54     if(!vis[n][n])
55     {
56         vis[n][n] = 1;
57         dfs(n,n);
58     }
59     printf("%d
",num*9);
60     return 0;
61 }

View Code