题意:两个人玩很变态的游戏,将一个草坪的某两个点点燃,点燃的草坪可以向上下左右四个方向扩散,问能否将整块草坪上面的草都点燃。如果能,输出最短时间(^_^他们就能玩更变态的游戏了),如果不能,输出-1.
思路:先求整个草坪的联通块数量cnt。
1.如果cnt大于2,一定不能点燃全图,输出-1
2.如果cnt等于2,分别在两个联通块枚举每个点中找最短时间,最后答案就是max(time1, time2)
3.如果cnt等于1,此题的关键点。枚举两个点作为bfs的两个起点,注意是两个起点,bfs求在这个两块中,到达任意一点至少需要的时间。最后的答案就是枚举的所有情况的最小时间。 PS:我用了另外一种判断最小时间,没考虑到一种特殊情况错了一下午。
AC代码
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> using namespace std; const int maxn = 15; char G[maxn][maxn]; int vis[maxn][maxn], d[maxn][maxn]; const int dx[] = {1,-1,0,0}; const int dy[] = {0,0,-1,1}; int n, m; void dfs(int x, int y, int flag) { vis[x][y] = flag; for(int i = 0; i < 4; ++i){ int px = x + dx[i], py = y + dy[i]; if(px < 0 || py < 0 || px >= n || py >= m) continue; if(G[px][py] == '#' && !vis[px][py]) dfs(px, py, flag); } } int bfs(int x, int y, int xx, int yy){ memset(d, -1, sizeof(d)); int ans = 0; queue<int>q; q.push(x * m + y); q.push(xx * m + yy); d[x][y] = d[xx][yy] = 0; while(!q.empty()) { int pos = q.front(); q.pop(); x = pos / m, y = pos % m; for(int i = 0; i < 4; ++i){ int px = x + dx[i], py = y + dy[i]; if(px < 0 || py < 0 || px >= n || py >= m) continue; if(G[px][py] == '#' && d[px][py] == -1){ d[px][py] = d[x][y] + 1; q.push(px * m + py); ans = max(ans, d[px][py]); } } } return ans; } int main(){ int T; scanf("%d", &T); int kase = 1; while(T--){ scanf("%d%d", &n, &m); for(int i = 0; i < n; ++i) scanf("%s", G[i]); printf("Case %d: ", kase++); memset(vis, 0, sizeof(vis)); int cnt = 0; for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) { if(G[i][j] == '#' && !vis[i][j]) { ++cnt; dfs(i, j, cnt); } } if(cnt > 2) printf("-1\n"); else if(cnt == 2) { int inf = 1 << 30; int ans[] = {inf, inf}; for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j){ if(G[i][j] == '#') { int h = vis[i][j] - 1; int a = bfs(i, j, i, j); ans[h] = min(ans[h], a); } } printf("%d\n", max(ans[0], ans[1])); } else if(cnt == 1){ int ans = 1 << 30; for(int i = 0; i < n * m; ++i) { int x1 = i / m, y1 = i % m; if(G[x1][y1] != '#') continue; for(int j = i + 1; j < n * m; ++j) { int x2 = j / m, y2 = j % m; if(G[x2][y2]!= '#') continue; int h = bfs(x1, y1, x2, y2); ans = min(ans, h); } } if(ans == 1 << 30) ans = 0; printf("%d\n", ans); } else if(cnt == 0) printf("-1\n"); } return 0; }
如有不当之处欢迎指出!