游客 注册 | 登录
中文 | En

4018 - 黑白图像

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

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

            

题目输入

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

题目输出

输出八连块的个数。

输入/输出样例

输入格式

6
100100
001010
000000
110000
111000
010100

输出格式

3

C语言解答

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char a[810][810];
int q[500000][2],f,r;
int dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1};
int n,m,t;

void bfs(int i,int j){ 
  int x,y,k;
  a[i][j]='0'; 
  f=0;r=1;q[r][0]=i;q[r][1]=j;
  while (f!=r){
	f++;
	x=q[f][0];y=q[f][1];
    for (k=0;k<8;k++)
    if ((x+dx[k]>=0)&&(x+dx[k]<n)&&(y+dy[k]>=0)&&(y+dy[k]<n)&&(a[x+dx[k]][y+dy[k]]=='1')) 
    {
        a[x+dx[k]][y+dy[k]]='0'; 
		r++;
		q[r][0]=x+dx[k];q[r][1]=y+dy[k];
     } 
  } 
}
void dfs(int x,int y)
{
	int k;
	for (k=0;k<8;k++)
	if (x+dx[k]>=0&&x+dx[k]<n&&y+dy[k]>=0&&y+dy[k]<n&&a[x+dx[k]][y+dy[k]]=='1')
	{ 
		a[x+dx[k]][y+dy[k]]='0';
		dfs(x+dx[k],y+dy[k]);                                                                    
	}  
}

int main(){
	int i,j;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
			scanf("%s",a[i]);

	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			if (a[i][j]=='1') {
				t++;
			dfs(i,j);
			}
	printf("%d\n",t);
    return 0;  
}

C++解答

#include<stdio.h>
#include<string.h>
char a[810][810];
int q[500000][2],f,r;
int dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1};
int n,m,t;
void bfs(int i,int j){
  int x,y,k;
  a[i][j]='0';
  f=0;r=1;
	q[r][0]=i;q[r][1]=j;
  while (f!=r){
    f++;
    x=q[f][0];y=q[f][1];
    for (k=0;k<8;k++)
    if ((x+dx[k]>=0)&&(x+dx[k]<n)&&(y+dy[k]>=0)&&(y+dy[k]<n)&&(a[x+dx[k]][y+dy[k]]=='1')){
			a[x+dx[k]][y+dy[k]]='0';
			q[++r][0]=x+dx[k];q[r][1]=y+dy[k];
		}
  }
}
int main(){
	int i,j;
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%s",a[i]);
	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			if (a[i][j]=='1') { t++;bfs(i,j); }
	printf("%d\n",t);
	return 0; 
}
请先登陆