admin管理员组

文章数量:1516870

An equidivision of an n × n square array of cells is a partition of the n 2 cells in the array in exactly n sets, each one with n contiguous cells. Two cells are contiguous when they have a common side.
A good equidivision is composed of contiguous regions. The figures show a good and a wrong equidivision for a 5×5 square:

问题链接 ：
问题简述 ：给定一个n*n的矩阵，其中放置n个数字，判定四连通的相同数字的个数是否都等于n？
问题分析 ：用DFS来解决，也可以用泛洪（Flood fill）算法来解决。输入处理有点繁琐。
程序说明 ：（略）
参考链接 ：（略）
题记 ：（略）

AC的C++语言程序如下： 

/* UVA11110 POJ3194 Equidivisions */#include<iostream>#include<cstdio>#include<cctype>#include<cstring>usingnamespace std;constint dr[]={0,0,1,-1};constint dc[]={1,-1,0,0};constint L =sizeof dr /sizeof dr[0];constint N =100;int n, g[N][N], vis[N][N];char s[1024];intdfs(int row,int col){
    vis[row][col]=1;int sum =1;for(int i =0; i < L; i++){int nextrow = row + dr[i];int nextcol = col + dc[i];if(0<= nextrow && nextrow < n &&0<= nextcol && nextcol < n &&
                vis[nextrow][nextcol]==0&& g[nextrow][nextcol]== g[row][col])
            sum +=dfs(nextrow, nextcol);}return sum;}intmain(){while(~scanf("%d",&n)&& n){getchar();memset(g,0,sizeof g);for(int i =1; i < n; i++){gets(s);int len =strlen(s);for(int j =0; j < len;){int r =0, c =0;while(j < len &&!isdigit(s[j])) j++;if(j >= len)break;while(j < len &&isdigit(s[j]))
                    r = r *10+ s[j++]-'0';while(j < len &&!isdigit(s[j])) j++;while(j < len &&isdigit(s[j]))
                    c = c *10+ s[j++]-'0';
                g[r -1][c -1]= i;}}memset(vis,0,sizeof vis);int flag =1;for(int i =0; flag && i < n; i++)for(int j =0; j < n; j++)if(vis[i][j]==0){if(dfs(i, j)!= n){
                        flag =0;break;}}puts(flag ?"good":"wrong");}return0;}

本文标签： 解决挑战掌握

版权声明：本文标题：从UVA到POJ，解决Equidivisions挑战：掌握DFS技巧 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.betaflare.com/web/1771807910a3269698.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。