学步园

题目大意：

中文翻译就不给了，英文不难能读懂。题目大意是给出一幅图画，统计上面每个色子的点数，‘*’表示色子的区域，注意并不一定是标准形状，相邻的‘X’表示一个点数，每个色子的点数从1-6.最后要从小到大地输出各个色子的点数。

读完题感觉这和前一篇日志里的油田问题差不多，仔细想想发现其实就是两次dfs，第一层dfs是深搜找‘*’，第二层dfs是找到‘X’后深搜找相邻的‘X’，所以整体难度不大。

通过这道题注意两个地方：

1、优先级队列的使用，默认是从大到小的优先顺序，如果要如题意要求从小到大必须如下声明

priority_queue<int,vector<int>,greater<int> > que;		//优先级队列默认是从大到小排的，只有这么写才是从小到大

2、输出格式要注意，如果你是presentation error，看看是不是这两点没有注意到：(1)最后一个数后面不能有空格（2）一个用例后要打印一空格行。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

char grid[55][55];
bool visit[55][55];
int w,h;
void searcharound(int x,int y)			//找到一个‘X’后遍历周围所有的‘X’
{
	if (x-1>=0&&grid[x-1][y]=='X'&&!visit[x-1][y]) 
	{
		visit[x-1][y]=1;
		searcharound(x-1,y);
	}
	if (x+1< h&&grid[x+1][y]=='X'&&!visit[x+1][y]) 
	{
		visit[x+1][y]=1;
		searcharound(x+1,y);
	}
	if (y-1>=0&&grid[x][y-1]=='X'&&!visit[x][y-1]) 
	{
		visit[x][y-1]=1;
		searcharound(x,y-1);
	}
	if (y+1< w&&grid[x][y+1]=='X'&&!visit[x][y+1]) 
	{
		visit[x][y+1]=1;
		searcharound(x,y+1);
	}
}
void dfs(int x,int y,int &Xcount)			//找到一个‘*’后遍历周围格子
{
	if (x<0||x>=h||y<0||y>=w) return;
	if (grid[x][y]=='*'&&!visit[x][y])		//如果是‘*’继续深搜
	{
		visit[x][y]=1;
		dfs(x-1,y,Xcount);
		dfs(x,y-1,Xcount);
		dfs(x,y+1,Xcount);
		dfs(x+1,y,Xcount);
	}
	else if (grid[x][y]=='X'&&!visit[x][y])	//如果是‘X’计数加1并调用searcharound后再深搜
	{
		Xcount++;
		visit[x][y]=1;
		searcharound(x,y);
		dfs(x-1,y,Xcount);
		dfs(x,y-1,Xcount);
		dfs(x,y+1,Xcount);
		dfs(x+1,y,Xcount);
	}
}

int main()
{
	int col=0;
	while(cin>>w>>h&&w&&h)
	{
		col++;
		memset(visit,0,sizeof(visit));
		int dotsnumber=0;
		priority_queue<int,vector<int>,greater<int> > que;		//优先级队列默认是从大到小排的，只有这么写才是从小到大
		for (int i=0;i<h;i++)
		{
			for (int j=0;j<w;j++)
			{
				cin>>grid[i][j];
			}
		}
		
		for (int i=0;i<h;i++)
		{
			for (int j=0;j<w;j++)
			{
				dfs(i,j,dotsnumber);
				if (dotsnumber!=0)
				{
					que.push(dotsnumber);
					dotsnumber=0;
				}
			}
		}
		cout<<"Throw "<<col<<endl;
		int len=que.size();
		for (int i=0;i<len;i++)
		{
			if (i==len-1) cout<<que.top();//特别要注意格式！最后一个后面不能有空格，否则报错！
			else  cout<<que.top()<<" ";
			que.pop();
		}
		cout<<endl<<endl;				//还要打印一空格行，小心！！
	}
	return 0;
}

转载请注明出处，谢谢！