当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,