机械加工网站模板,软件开发一般多少钱,优秀界面设计案例,猎头公司面试一般会问什么问题题目链接#xff1a;http://poj.org/problem?id2157 题意#xff1a;给一张地图#xff0c;地图里有门和钥匙#xff0c;想要开门必须集齐所有钥匙。给定起点和终点#xff0c;问从起点出发能否到达终点。 爆搜floodfill#xff0c;每填一次考虑是否到达终点#xff0c…题目链接http://poj.org/problem?id2157 题意给一张地图地图里有门和钥匙想要开门必须集齐所有钥匙。给定起点和终点问从起点出发能否到达终点。 爆搜floodfill每填一次考虑是否到达终点并且把门都开开钥匙都拿上再进行下一次其实可以不重复200次备份一下上一次的状态图再比对floodfill后的与当前的是否不同即可。 1 #include algorithm2 #include iostream3 #include iomanip4 #include cstring5 #include climits6 #include complex7 #include cassert8 #include cstdio9 #include bitset
10 #include vector
11 #include deque
12 #include queue
13 #include stack
14 #include ctime
15 #include set
16 #include map
17 #include cmath
18 using namespace std;
19
20 const int maxn 22;
21 const int dx[5] {1, -1, 0, 0};
22 const int dy[5] {0, 0, 1, -1};
23 int n, m;
24 int sx, sy;
25 int kn[6], ck[6];
26 char G[maxn][maxn], H[maxn][maxn];
27 bool vis[maxn][maxn];
28 bool done;
29
30 bool ok(int x, int y) {
31 return x 0 y 0 x n y m;
32 }
33
34 void dfs(int x, int y) {
35 if(done) return;
36 if(vis[x][y]) return;
37 vis[x][y] 1;
38 for(int i 0; i 4; i) {
39 int xx x dx[i];
40 int yy y dy[i];
41 if(!ok(xx, yy)) continue;
42 if(G[xx][yy] X) continue;
43 if(vis[xx][yy]) continue;
44 if(G[xx][yy] A G[xx][yy] E) {
45 if(ck[G[xx][yy]-A] kn[G[xx][yy]-A]) {
46 G[xx][yy] .;
47 dfs(xx, yy);
48 }
49 }
50 else if(G[xx][yy] a G[xx][yy] e) {
51 ck[G[xx][yy]-a];
52 G[xx][yy] .;
53 dfs(xx, yy);
54 }
55 else if(G[xx][yy] G) {
56 done 1;
57 return;
58 }
59 else if(G[xx][yy] .) dfs(xx, yy);
60 }
61 }
62
63 int main() {
64 // freopen(in, r, stdin);
65 while(~scanf(%d%d,n,m)nm) {
66 memset(kn, 0, sizeof(kn));
67 memset(ck, 0, sizeof(ck));
68 memset(G, 0, sizeof(G));
69 memset(vis, 0, sizeof(vis));
70 for(int i 0; i n; i) scanf(%s, G[i]);
71 for(int i 0; i n; i) {
72 for(int j 0; j m; j) {
73 if(G[i][j] a G[i][j] e) kn[G[i][j]-a];
74 if(G[i][j] S) sx i, sy j;
75 }
76 }
77 done 0;
78 for(int _ 0; _ 200; _) {
79 memset(vis, 0, sizeof(vis));
80 dfs(sx, sy);
81 if(done) break;
82 }
83 if(done) puts(YES);
84 else puts(NO);
85 }
86 return 0;
87 } 转载于:https://www.cnblogs.com/kirai/p/6437978.html
