题意很明显，而且需要注意的地方在第一个测试例子已经有所体现了。就是同一时刻可能有多个水滴到达一个点，而且该位置的水滴爆破了，但也只会产生四个方向各一个水滴
所以，必须处理好同一个时刻的水滴，所以用了俩个队列来处理，将同一个时刻的水滴放在一个队列中，让所有水滴都飞行一个单位时间，如果没有碰到水滴，则压入另一个队列，如果碰到了，则在该位置直接加1， 等处理完其他同一时刻的水滴之后，再判断是否存在会爆的水滴，如果会，则再产生四个水滴，压入另一个队列，以此类推，，具体看代码：
hdu4527
#include<iostream> #include<algorithm> #include<queue> using namespace std; const int N = 6; int g[N][N]; int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; struct node { int x, y, k; node(){} node(int xx, int yy, int kk):x(xx), y(yy), k(kk){} }; queue<node> Q[2]; void solve() { int id = 0; while(true) { while(!Q[id & 1].empty()) { node cur = Q[id & 1].front(); Q[id & 1].pop(); int x = cur.x + dir[cur.k][0]; int y = cur.y + dir[cur.k][1]; if( x < 0 || x >= N || y < 0 || y >= N ) continue; if(g[x][y] == 0) Q[(id + 1) & 1].push(node(x, y, cur.k)); else g[x][y]++;//累加后再对会爆破的水滴处理，针对第一个测试例子就知道了 } //cout << Q[(id + 1) & 1].size() << endl; for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) if(g[i][j] >= 5) { g[i][j] = 0; for(int k = 0; k < 4; ++k) { Q[(id + 1) & 1].push(node(i, j, k)); } } if(Q[(id + 1) & 1].empty()) break; ++id; } } int main() { int m; while(scanf("%d %d %d %d %d %d",&g[0][0], &g[0][1], &g[0][2], &g[0][3],&g[0][4], &g[0][5]) == 6) { for(int i = 1; i < N; ++i) for(int j = 0; j < N; ++j) scanf("%d",&g[i][j]); scanf("%d",&m); while(m--) { int x, y; scanf("%d %d",&x, &y); --x, --y; g[x][y]++; if(g[x][y] >= 5) { g[x][y] = 0; for(int i = 0; i < 4; ++i) Q[0].push(node(x, y, i)); } solve(); } for(int i = 0; i < N; ++i) { printf("%d",g[i][0]); for(int j = 1; j < N; ++j) printf(" %d",g[i][j]); puts(""); } puts(""); } return 0; }
同样是中文题，搜索，关键在于，'E' 跟'D' 的位置是不会改变的，即使找到其中一个人，该位置的人也不会消失，这个幸好从测试例子里面发现了。
一开始以为每一个位置只可能走过一次，，敲完之后果断WA了，后来自己写的一个测试例子发现了问题，同一个位置未必只能走一次，有可能必须再走一次
5 6 3
XXDX . .
. . . X E .
. . . . X .
. . . . S .
. . . . . .
这样就需要考虑，再走一遍到底有没有用，，或许不需要想那么多，想再经过这一个点一遍，那之前走过这个点到再回到这个点是否做了有用功，也就是是否能找到一个人或俩个人，如果状态发生改变了，那就应该允许该点回来。。所以用vis[x][y][4]， 只有俩个人，所以总共有4个状态。。
hdu4528
#include<iostream> #include<algorithm> #include<queue> #include<stdio.h> #include<stdlib.h> #include<string.h> using namespace std; const int N = 100 + 10; char g[N][N]; int n, m, t; int sx, sy, dx, dy, ex, ey; bool vis[N][N][4]; int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; struct node { int x, y, step; int state; node(){} node(int xx, int yy, int st):x(xx), y(yy), step(st){ state = 0;} }; int BFS() { memset(vis, false, sizeof(vis)); queue<node> Q; Q.push(node(sx, sy, 0)); vis[sx][sy][0] = true; while(!Q.empty()) { node cur = Q.front(); Q.pop(); if(cur.step > t) return -1; for(int k = 0; k < 4; ++k) { int x = cur.x + dir[k][0], y = cur.y + dir[k][1]; if(x < 0 || x >= n || y < 0 || y >= m) continue; bool flag = false; if(!(cur.state & 1) && (dx == cur.x || dy == cur.y)) flag = true; if(!(cur.state & 2) && (ex == cur.x || ey == cur.y)) flag = true; if(!flag) continue;//判断是否应该沿该方向搜一下能否看到一个人 while(true)//沿该方向搜一下能否看到一个人 { if(g[x][y] == 'X') break; if(g[x][y] == 'D') { cur.state |= 1; break; } if(g[x][y] == 'E') { cur.state |= 2; break; } x += dir[k][0], y += dir[k][1]; if(x < 0 || x >= n || y < 0 || y >= m) break; } } if(cur.state == 3) { return cur.step; } for(int k = 0; k < 4; ++k) { int x = cur.x + dir[k][0], y = cur.y + dir[k][1]; if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y][cur.state] || g[x][y] == 'X') continue; if(g[x][y] == 'D' || g[x][y] == 'E') continue;//'D' 跟 'E'也是不能经过的 vis[x][y][cur.state] = true; node tmp = node(x, y, cur.step + 1); tmp.state = cur.state; Q.push(tmp); } } return -1; } int main() { int T, cas = 0; scanf("%d",&T); while(T--) { scanf("%d %d %d",&n, &m, &t); for(int i = 0; i < n; ++i) { scanf("%s",g[i]); for(int j = 0; j < m; ++j) { if(g[i][j] == 'S') sx = i, sy = j; if(g[i][j] == 'E') ex = i, ey = j; if(g[i][j] == 'D') dx = i, dy = j; } } g[sx][sy] = '.'; int ans = BFS(); printf("Case %d:\n%d\n", ++cas, ans); } return 0; }