// 题意：给一个图案，其中'.'表示背景，非'.'字符组成的连通块为筛子。每个筛子里又包含两种字符，其中'X'组成的连通块表示筛子上的点
// 统计每个筛子里有多少个“X”连通块
思路：两次dfs
//思路：先dfs找包含X和*的区域，再在*的区域中dfs X的个数 #include<cstdio> #include<cstring> #include<iostream> #include<string> #include<algorithm> #include<vector> using namespace std; const int N=52; char pic[N][N]; int idx[2][N][N]; vector<int> ans; int w, h; int dr[]={0, 1, 0, -1}; int dc[]={1, 0, -1, 0}; //type 0 . //type 1 . and * bool isOk(int r, int c, int type) { if(type==0) { if(idx[type][r][c] || r <0 || r >=h || c <0 || c >=w || pic[r][c]=='.') return false; } else if(type==1) { if(idx[type][r][c] || r <0 || r >=h || c <0 || c >=w || pic[r][c]!='X') return false; } return true; } void dfs(int r, int c, int cnt) { if(!isOk(r, c, 0)) return; idx[0][r][c]=cnt; for(int i=0;i<4;i++) { int nr=r+dr[i]; int nc=c+dc[i]; dfs(nr, nc, cnt); } } void dfs2(int r, int c) { if(!isOk(r, c, 1)) return; idx[1][r][c]=idx[0][r][c]; for(int i=0;i<4;i++) { int nr=r+dr[i]; int nc=c+dc[i]; dfs2(nr, nc); } } void dump(int type) { for(int i=0;i<h;i++) { for(int j=0;j<w;j++) printf("%d", idx[type][i][j]); printf(" "); } printf(" "); } int main() { #ifndef ONLINE_JUDGE freopen("./uva657.in", "r", stdin); #endif int kase=0; while(scanf("%d %d", &w, &h)!=EOF && w && h) { for(int i=0;i<h;i++) scanf("%s", pic[i]); memset(idx, 0, sizeof idx); ans.clear(); int cnt=0; for(int i=0; i<h; i++) for(int j=0;j<w;j++) { //搜索 X 和 *（即骰子）， 并在 idx[0]中 标记骰子的序号 if(!idx[0][i][j] && pic[i][j]=='X') { cnt++; dfs(i, j, cnt); } //搜索骰子中的 X ，并统计骰子的连通点的个数 if(!idx[1][i][j] && pic[i][j]=='X') { dfs2(i, j); if(ans.size()<idx[0][i][j]) ans.resize(idx[0][i][j]); ans[idx[0][i][j]-1]++; } } //dump(0); //dump(1); sort(ans.begin(), ans.end()); printf("Throw %d ", ++kase); int n=ans.size(); for(int i=0; i<n-1; i++) printf("%d ", ans[i]); if(n) printf("%d", ans[n-1]); printf(" "); } return 0; }
lrj解法：
// UVa657 The die is cast // Rujia Liu // 题意：给一个图案，其中'.'表示背景，非'.'字符组成的连通块为筛子。每个筛子里又包含两种字符，其中'X'组成的连通块表示筛子上的点 // 统计每个筛子里有多少个“X”连通块 // 算法：首先用DFS找出两类连通块，即筛子（'.'与'X'）和点（'X'），类别用0和1表示，然后统计0类连通块和1类连通块之间的包含关系，最后输出结果 // 在代码中，cnt[i]为第i类连通块的个数，idx[i][r][c]为格子(r,c)处第i类连通分量的编号 // enclose[i][j]表示编号为i的第0类连通块是否包含编号为j的第1类连通块 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 50; // 图片边长的最大值 const int maxd = 1000; // 筛子的最大个数 const int dr[] = {-1, 1, 0, 0}; const int dc[] = {0, 0, -1, 1}; char pic[maxn][maxn]; int h, w, idx[2][maxn][maxn], cnt[2]; int enclose[maxd][maxd*6]; bool is_type(int type, char ch) { if(type == 0) return ch != '.'; // 筛子（包括点） return ch == 'X'; // 点 } // DFS找第type类联通块，赋予编号id void dfs(int r, int c, int type, int id) { if(r < 0 || r >= h || c < 0 || c >= w) return; if(!is_type(type, pic[r][c])) return; if(idx[type][r][c] > 0) return; idx[type][r][c] = id; for(int d = 0; d < 4; d++) dfs(r+dr[d], c+dc[d], type, id); } // 标记(r,c)处的0类连通块包含编号为id的1类连通块 void mark(int r, int c, int id) { if(r >= 0 && r < h && c >= 0 && c < w) enclose[idx[0][r][c]][id] = 1; } int main() { int kase = 0; while(scanf("%d%d", &w, &h) == 2 && w) { for(int i = 0; i < h; i++) scanf("%s", pic[i]); // DFS求连通块 memset(idx, 0, sizeof(idx)); cnt[0] = cnt[1] = 0; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) for(int t = 0; t < 2; t++) { if(idx[t][i][j] == 0 && is_type(t, pic[i][j])) dfs(i, j, t, ++cnt[t]); } // 计算包含关系 memset(enclose, 0, sizeof(enclose)); for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) if(pic[i][j] == 'X') for(int d = 0; d < 4; d++) mark(i+dr[d], j+dc[d], idx[1][i][j]); // 统计点数。注意两类连通块均从1开始编号 int ans[maxd]; for(int i = 1; i <= cnt[0]; i++) { ans[i] = 0; for(int j = 1; j <= cnt[1]; j++) if(enclose[i][j]) ans[i]++; } sort(ans+1, ans+cnt[0]+1); // 输出。注意行末不要输出多余空格 printf("Throw %d ", ++kase); for(int i = 1; i < cnt[0]; i++) printf("%d ", ans[i]); printf("%d ", ans[cnt[0]]); } return 0; }