首页 > 代码库 > 华为题 搜索水题 DFS

华为题 搜索水题 DFS

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <string>
 6 #include <iterator>
 7 #include <algorithm>
 8 #include <cstdlib>
 9 #include <deque>
10 #include <queue>
11 #include <stack>
12 #include <map>
13 #include <vector>
14 #include <set>
15 #include <list>
16 using namespace std;
17 #define PI acos(-1.0)
18 #define INF 0x3f3f3f3f
19 #define MAX 1005
20 #define MST(a,b) memset(a,b,sizeof(a))
21 #define MOD 20121223
22 #define EPS 1e-6
23 #define pp(a) cout << a << endl;
24 typedef long long LL;
25 typedef unsigned long long LLU;
26 char m[MAX][MAX];
27 int r,c;
28 int finde;
29 int dx[] = {0,0,-1,1};
30 int dy[] = {1,-1,0,0};
31 int vis[MAX][MAX];
32 void dfs(int x,int y) {
33     if(m[x][y] == H) {
34         finde = 1;
35         return ;
36     }
37     for(int i = 0;i < 4;i ++) {
38         int nx = x + dx[i];
39         int ny = y + dy[i];
40         if(nx >= 0 && nx < r && ny >= 0 && ny < c && m[nx][ny] != # && !vis[nx][ny]) {
41             vis[nx][ny] = 1;
42             dfs(nx,ny);
43             if(finde) return ;
44             vis[nx][ny] = 0;
45         }
46     }
47 }
48 int main(void) {
49     finde = 0;
50     MST(vis,0);
51     cin >> r;
52     cin >> c;
53     int x,y;
54     for(int i = 0;i < r;i ++) {
55         for(int j = 0;j < c;j ++) {
56             cin >> m[i][j];
57             if(m[i][j] == B) {
58                 x = i;
59                 y = j;
60             }
61         }
62     }
63     dfs(x,y);
64     if(finde) cout << "Y" << endl;
65     else cout << "N" << endl;
66     return 0;
67 }