黑白图像-入门级深搜

黑白图像

Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte
Total Submit:282 Accepted:82

Description

输入一个n×n的黑白图像（1表示黑色，0表示白色），任务是统计其中八连块的个数。如果两个黑格子有公共边或者公共顶点，就说它们属于同一个八连块。如下图所示的图形有3个八连块。

Input

第1行输入一个正整数n（n≤700），此后输入n行，每行是由n个0或1组成的字符串。

Output

在输入黑白图像中，八连块的个数

Sample Input

6
100100
001010
000000
110000
111000
010100

Sample Output

3

Source

刘汝佳《算法竞赛入门经典》

题目链接：http://acm.njupt.edu.cn/acmhome/problemdetail.do?method=showdetail&id=1102

#include<stdio.h>
#include<memory.h>
const int MAXN=1000;
void dfs(int i,int j);
char vis[MAXN][MAXN],mat[MAXN][MAXN];
int n;
int main()
{
	//freopen("in.in","r",stdin);
	int i,j,count;
	while(scanf("%d",&n)!=EOF)
	{
		memset(vis,1,sizeof(char)*MAXN*MAXN);
	    memset(mat,0,sizeof(char)*MAXN*MAXN);
		for(i=1;i<=n;i++){
	    	scanf("%s",mat[i]);
			for(j=n;j>=1;j--)
				mat[i][j]=mat[i][j-1]-'0';
			mat[i][0]=0;
		}
     	for(i=1,count=0;i<=n;i++)
			for(j=1;j<=n;j++)
				if(mat[i][j]&&vis[i][j]){
					count++;
					dfs(i,j);
				}
		printf("%d\n",count);
	}
	return 0;
}

void dfs(int i,int j)       //搜黑图
{
	if(!mat[i][j]||!vis[i][j])return;
	vis[i][j]=0;
	dfs(i-1,j-1),dfs(i-1,j),dfs(i-1,j+1);
	dfs(i,j-1),               dfs(i,j+1);
	dfs(i+1,j-1),dfs(i+1,j),dfs(i+1,j+1);	
}