深度搜索算法3(c++)插图

#include 
#include 
using namespace std;
int a[110][110];
char b[110][110];
int n,m;
int si,sj,ei,ej;
int di[] = {0,1,0,-1};
int dj[] = {1,0,-1,0};
void aaa(int,int,int);
int main()
{
	while(true)
	{
		cin>>n>>m;
		if(n==0&&m==0) break;
		for(int i = 0;i<n;i++)
		{
			for(int j = 0;j>b[i][j];
				if(b[i][j]!='#')
				{
					a[i][j] = 1000000;
				}
				else{
					a[i][j] = 0;
				}
				if(b[i][j]=='@')
				{
					si = i;
					sj = j;
				}
				else if(b[i][j]=='*')
				{
					ei = i;
					ej = j;
				}
			}
		}
		aaa(si,sj,0);
		if(a[ei][ej]<100000)
		{
			cout<=0&&ti=0&&tjcnt+1&&b[ti][tj]!='#')
		{
			aaa(ti,tj,cnt+1);
			
		}
	}
	
	return;
}

卫星照片

农夫约翰总是想要一个农场的地图,所以他拍摄了一张N行M列的卫星照片。 一部分的照片看起来像这样: 他认为每个联通块都是一个谷仓或一头奶牛。 农夫约翰认为一个联通块是谷仓,当且仅当它是一个完整的矩形,否则该联通块是一头奶牛。

在下面的照片中,有三个谷仓(大小分别为2×1,2×5和1×1)和两头奶牛。 计算他的卫星照片中谷仓和奶牛的数量。

. . . . . . . . . . . . . . . . . .
. . # # # # # . . . . . . . # # . .
. . # # # # # . . . . . . # # . . .
. . . . . . . . . . . . . . . . . .
# . . . . . . . # # # . . . . . # .
# . . . . . # # # # # . . . . . . .

输入

行1:两个空格分隔的整数:N和M

 行2..N + 1:行i + 1表示照片的行i包含M个字 符(且不含空格)。

输出

行1:照片中的谷仓数量。

行2:照片中的奶牛数量。

#include 
#include 
using namespace std;
int a[110][110];
char b[110][110];
int n,m;
int si,sj,ei,ej;
int di[] = {0,1,0,-1};
int dj[] = {1,0,-1,0};
int ck = 0,nn = 0;
int cnt = 0;
void aaa(int,int);
int main()
{
	cin>>n>>m;
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j>b[i][j];
		}
	}
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<m;j++)
		{
			if(b[i][j]=='#')
			{
				si = i;
				ei = i;
				sj = j;
				ej = j;
				cnt = 0;
				aaa(i,j);
				if(cnt==(ei-si+1)*(ej-sj+1))
				{
					ck++;
				}
				else{
					nn++;
				}
			}
		}
	}
	cout<<ck<<endl<<nn;
	return 0;
}
void aaa(int i,int j)
{
	b[i][j] = '.';
	cnt++;
	si = min(si,i);
	sj = min(sj,j);
	ei = max(ei,i);
	ej = max(ej,j);
	for(int qqq = 0;qqq=0&&ti=0&&tj<m&&b[ti][tj]=='#')
		{
			aaa(ti,tj);
			
		}
	}
	
	return;
}

本站无任何商业行为
个人在线分享 » 深度搜索算法3(c++)
E-->