起初学习dfs的时候 看不懂这个题目 回过头来今天看的时候思路相对比较清晰了。但还是想不到怎么处理 查询有多少个空白洞。并且一个图中还有好多个象形字符。网上思路是 在周围扩展一圈0，使得文字之外的所有0 都连通，一次dfs标记所有文字之外的0为-1。然后遍历图，发现1就沿着有1 的路径dfs2，在这个过程中，如果发现0，那么必然是文字内部的空洞，此时把空洞dfs 置为-1，标记以后不再走。那么发现几次0就有几个空洞在文字中。那么每一次的dfs2，就处理了一个象形文字。cnt的值就是空洞的个数即文字特征量。感觉这题目相当有价值。
有一处值得学习的地方，字符串常量的运用。
奇怪的地方时在hdu oj上提交 是栈溢出，，而在uva上却过了。
#include<iostream>#include<stdio.h>#include<string.h>using namespace std;const int INF=210;int n,m,cnt;char cn[6]= {'A','D','J','K','S','W'};char str[]= {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};int dir[][4]= {{-1,0},{0,-1},{1,0},{0,1}};int G[INF][INF];int s[16][4]={{0,0,0,0},{0,0,0,1},{0,0,1,0},{0,0,1,1},{0,1,0,0},{0,1,0,1},{0,1,1,0},{0,1,1,1},{1,0,0,0},{1,0,0,1},{1,0,1,0},{1,0,1,1},{1,1,0,0},{1,1,0,1},{1,1,1,0},{1,1,1,1}};void input(){char ch;memset(G,0,sizeof(G));for(int i=1; i<=n; i++){getchar();int len=1;for(int j=1; j<=m; j++){scanf("%c",&ch);for(int k=0; k<16; k++){if(ch==str[k]){for(int t=0; t<4; t++)G[i][len++]=s[k][t];break;}}}}}bool inG(int x,int y){if(x>=0&&x<=n+1&&y>=0&&y<=m+1)return 1;return 0;}void dfs(int x,int y){if(!inG(x,y)||G[x][y]!=0)return ;G[x][y]=-1;for(int i=0; i<4; i++){int tx=x+dir[i][0];int ty=y+dir[i][1];dfs(tx,ty);}}void dfs2(int x,int y){if(!inG[x][y]||G[x][y]==-1)return ;if(!G[x][y]){dfs(x,y);cnt++;return ;}G[x][y]=-1;for(int i=0; i<4; i++){int tx=x+dir[i][0];int ty=y+dir[i][1];dfs2(tx,ty);}}int main(){int ca=1;int num[10];while(scanf("%d%d",&n,&m)==2&&n+m){memset(G,0,sizeof(G));memset(num,0,sizeof(num));input();m*=4;dfs(0,0);for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(G[i][j]==1){cnt=0;dfs2(i,j);if(cnt==0)num[5]++;else if(cnt==2)num[3]++;else if(cnt==3)num[2]++;else if(cnt==4)num[4]++;else if(cnt==1)num[0]++;else num[1]++;}}}printf("Case %d: ",ca++);for(int i=0; i<6; i++)while(num[i]–)printf("%c",cn[i]);printf("\n");}return 0;}
向上攀爬的。
