poj 1111(Image Perimeters DFS)

1254 ワード


この問題は実は私はすべてどんな意味を理解していないで、同じくあまりよく見ていないで、ブログの中であるyuanのブログの中でその題意を言い出したかどうかを見てみたいと思って、意外にも小さくありません
心は周長を求める方法を見て、もとはPerimetersは周長の意味です!!!そばにいくつかの点があって周長に1をプラスして、この機能をプラスしました
すでに、前にdfsで8連通のすべてのブロック数を見つければいいです.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char a[105][105];
int step[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};
int step1[4][2]={-1,0,1,0,0,-1,0,1};
int len;
void dfs(int x,int y)
{
    	a[x][y]='*';
    	for(int i=0;i<4;i++)
    	{
    		int k1=x+step1[i][0];
    		int k2=y+step1[i][1];
    		if(a[k1][k2]=='.')
    			len++;
    	}
		for(int i=0;i<8;i++)
		{
			int p=x+step[i][0];
			int q=y+step[i][1];
			if(a[p][q]=='X')
			{
				dfs(p,q);
			}
		}
}
int main()
{
	int m,n,x,y,i,j;
	while(scanf("%d%d%d%d",&m,&n,&x,&y),m!=0&&n!=0&&x!=0&&y!=0)
	{
		getchar();
		len=0;
		for(i=0;i<=m+1;i++)
		{
			a[0][i]='.';
			a[m+1][i]='.';
			a[i][0]='.';
			a[i][n+1]='.';
		}
		for(i=1;i<=m;i++)
			{
				for(j=1;j<=n;j++)
				{
					scanf("%c",&a[i][j]);
				}
				getchar();
			}
		dfs(x,y);
		printf("%d
",len); } }