【例题 6-13 UVA - 1103】Ancient Messages

在这里输入题意

【题解】

每个图案里面的“洞”的个数都是不同的。
则可以根据这个判别每个图像是什么。
先用dfs确定轮廓之后。
再从每个白点出发dfs,遇到的黑点且没有到达过边界,那么它就是所遇到的黑点里面的“洞”;
计算每个轮廓有多少个"洞"就好

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 200;

const int dx[5] = {0,0,0,1,-1};

const int dy[5] = {0,1,-1,0,0};

int n,m,a[N+10][N+10],flag[N+10][N+10];//flag>0 black block flag <0 white but visited

int cnt,hole[N*N+10];

char s[N+10][N+10];

int touch;

char duiying[100];

vector <char> v;

void cl(int x,int y,int col){

	int num = isdigit(s[x][y])?(s[x][y]-'0'):(s[x][y]-'a'+10);

 	for (int j = col+3;j >= col;j--){

 		a[x][j] = num&1;

 		num>>=1;

	}

}

void dfs(int x,int y){

	if (x<0 || x>=n || y<0 || y>=m) return;

	if (flag[x][y]!=0) return;

	if (a[x][y]==0) return;

	flag[x][y] = cnt;

	for (int i = 1;i <= 4;i++) dfs(x+dx[i],y+dy[i]);

}	

void dfs1(int x,int y){

	if (x<0 || x>=n || y <0 || y>=m){

		touch = -1;

		return;

	}

	if (flag[x][y]==-1) return;

	if (flag[x][y]>0){

		if (touch!=-1) touch = flag[x][y];

		return;

	}

	flag[x][y] = -1;

	for (int i = 1;i <= 4;i++) dfs1(x+dx[i],y+dy[i]);

}

int main(){

//	freopen("rush.txt","r",stdin);

	duiying[1] = 'A',duiying[3] = 'J',duiying[5] = 'D',duiying[4] = 'S',duiying[0] = 'W',duiying[2] = 'K';

	int kase = 0;

	while (~scanf("%d%d",&n,&m) && n && m){

		for (int i = 0;i < n;i++) scanf("%s",s[i]);

		for (int i = 0;i < n;i++){

			int cnt = 0;

			for (int j = 0;j < m;j++){

				cl(i,j,cnt);

				cnt+=4;

			}

		}

		m*=4;

		memset(flag,0,sizeof flag);

		cnt = 0;

		for (int i = 0;i < n;i++)

			for (int j = 0;j < m;j++)

				if (a[i][j] && flag[i][j]==0){

					++cnt;

					dfs(i,j);

				}

/*

		for (int i = 0;i < n;i++){

	    	for (int j = 0;j < m;j++)

		    	printf("%3d",flag[i][j]);

		    puts("");

		}

*/

		memset(hole,0,sizeof hole);

		for (int i = 0;i < n;i++)

			for (int j = 0;j < m;j++)

				if (a[i][j]==0 && flag[i][j]==0){

				    touch = 0;

					dfs1(i,j);

					if (touch==-1) continue;

					hole[touch]++;

				}

//		printf("hole0=%d\n",hole[0]);

		v.clear();

		for (int i = 1;i <= cnt;i++)

			v.push_back(duiying[hole[i]]);

		sort(v.begin(),v.end());

		printf("Case %d: ",++kase);

		for (int i = 0;i < (int) v.size();i++) putchar(v[i]);

		puts("");

	}

	return 0;

}

巴特西

【例题 6-13 UVA - 1103】Ancient Messages

最新文章

热门文章