uva657 persentation error的看过来!
题目大意:
中文翻译就不给了,英文不难能读懂。题目大意是给出一幅图画,统计上面每个色子的点数,‘*’表示色子的区域,注意并不一定是标准形状,相邻的‘X’表示一个点数,每个色子的点数从1-6.最后要从小到大地输出各个色子的点数。
读完题感觉这和前一篇日志里的油田问题差不多,仔细想想发现其实就是两次dfs,第一层dfs是深搜找‘*’,第二层dfs是找到‘X’后深搜找相邻的‘X’,所以整体难度不大。
通过这道题注意两个地方:
1、优先级队列的使用,默认是从大到小的优先顺序,如果要如题意要求从小到大必须如下声明
[cpp]
priority_queue<int,vector<int>,greater<int> > que; //优先级队列默认是从大到小排的,只有这么写才是从小到大
2、输出格式要注意,如果你是presentation error,看看是不是这两点没有注意到:(1)最后一个数后面不能有空格(2)一个用例后要打印一空格行。
[cpp]
#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;
}
补充:软件开发 , C++ ,