//好题,最关键是如何建图 #include<iostream> #include<fstream> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #include<stack> #include<vector> #include<set> #include<ctype.h> #include<algorithm> #include<string> #define PI acos(-1.0) #define maxn 100000 #define INF 1<<25 #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; using namespace std; int w, h, grid, mx; int g[230][230], vis[230][230]; int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; bool in(int x, int y) { return (x >= 0 && x < h && y >= 0 && y < w); } void flood_fill(int x, int y, int color) { int nx, ny, i; vis[x][y] = 1, g[x][y] = color; for (i = 0; i < 4; i++) { nx = x + dir[i][0], ny = y + dir[i][1]; if (in(nx, ny) && !vis[nx][ny] && !g[nx][ny]) flood_fill(nx, ny, color); } } void boundary() { int i, j; for (i = 0; i < h; i++) { if (!g[i][0] && !vis[i][0]) flood_fill(i, 0, 2); if (!g[i][w - 1] && !vis[i][w - 1]) flood_fill(i, w - 1, 2); } for (j = 0; j < w; j++) { if (!g[0][j] && !vis[0][j]) flood_fill(0, j, 2); if (!g[h - 1][j] && !vis[h - 1][j]) flood_fill(h - 1, j, 2); } } void dfs(int x, int y) { int nx, ny, i; vis[x][y] = 1; grid++; for (i = 0; i < 4; i++) { nx = x + dir[i][0], ny = y + dir[i][1]; if (in(nx, ny) && !vis[nx][ny] && !g[nx][ny]) dfs(nx, ny); } } int main () { int cas = 1, i, j; char ch; while(cin>>w>>h) { if (w + h == 0) break; mem(g, 0); mem(vis, 0); h *= 3, w *= 3; for (i = 1; i < h; i += 3) for (j = 1; j < w; j += 3) { cin>>ch; if (ch == ‘\\‘) g[i - 1][j - 1] = g[i][j] = g[i + 1][j + 1] = 1; else g[i - 1][j + 1] = g[i][j] = g[i + 1][j - 1] = 1; } boundary(); int cyl = 0; mx = 0; for (i = 0; i < h; i++) for (j = 0; j < w; j++) if (!g[i][j] && !vis[i][j]) { grid = 0; dfs(i, j); if (grid >= 12) cyl++; if (grid > mx) mx = grid; } printf("Maze #%d:\n", cas++); if (cyl) printf("%d Cycles; the longest has length %d.\n", cyl, mx / 3); else printf("There are no cycles.\n"); printf("\n"); } return 0; }
原文:http://blog.csdn.net/sio__five/article/details/18910097