FZU-2150 Fire Game(暴力+広捜)

19878 ワード
検索
テーマリンク:http://acm.fzu.edu.cn/problem.php?pid=2150クリックしてリンクを開く
Problem 2150 Fire Game
Accept:2540    Submit:8781 Time Limit:1000 mSec    メモリLimit:32768 KB
 Problem Description
Fat breother and Maze ararare playing a kind of special game on n*M board(N rows,M columns).At the begining、each grids of thisboard is is consisting of grasor just juseemipty and then thethethe thethe the the theyfistststrerereredededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededew,the fire can spread among the grass.If the grid(x,y)is firing at time t,the grid whihihich is adjacent to thisgrisgrid will fire at+1 which refersto the grid(x+1,y),(x+1,y),(x-1,x-1,x))ininininininininininininininininininininine e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e ing of grass is get fired、Fat broother and Maze will stand in the middle of the grid and playing a MORE special game.(Maybot’s the OOXX game which decrypted in the last proble,who knows.)
You can asome that the grass in the board would never out and the empy grid would never get fire.
Note that the two grids the y chose can be the same.
 Input
The first line of the date is an integer T,which is the number of the text cases.
The n T cases follow、each case contains two integers N and M indicate the size of the board.The n goes N line、each line with M character shows the board.「噗」Indicates the grass.Youcant.Youcant.com the stress Indicates.
1<=T<=100,1<=n==10,1<=m<=10
 Output
For each case,output the case number first,if they can play the MORE special game(hentai)game(fire all the grast)、output the minimal time the y need to wait after the set fire,ot the.put.put.put.put.put
 Sample Input
43.シ.ハ.ハ.ハ.ハ.ハ.ハ.ハ.シ.シ.シ.シ.シ.シ.シ.シ.シ.シ.シ.シ.シ.シ.シ.ハ.3…シ.ハ.シ…3ハ.シ
 Sample Output
Case 1:1 Case 2:-1 Case 3:0 Case 4:2
いいテーマがfzuだった.良くないことは何もないです.サーバーemmです.
最初にこの問題を手に入れたら面倒くさいと思います.分類して検討しなければなりません.
草の接続度を確定するのは1であるかもしれません.  2 >2 
   1のために2つの起点を暴力的に検索し、最小のステップ数を探す(2枚の図は2つの火元のステップ数を記録する).
   2つの点をそれぞれに分けて検索する場合は、この時点で最も速く蔓延する全ての方法を探す(最初はxy方向の最大位置最小位置だけを判断する必要があると思っていたが、後には間違っていた.蔓延方法は1つしかないかもしれないので)も同じです.   広く一つ一つの点を検索して列挙する.
   とするなら  -1
そして午後にかけました.コード長の恐怖
そして題解を検索したら、直接に12合併暴力を二つの点に検索すればいいです.
もちろん最初はこういう考え方が鍛えられました.捜索に対する能力はwarchessとこの問題を経験してから明らかに向上しました.
ほらを吹いてはいけません.
先に12000 bコードを払います
縮めるのがみっともないです.誰も見ていないでしょう.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
struct xjy
{
    int x,y;
};
xjy b,e;
int n,m,k;
queue  q;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
char mmap1[20][20];
char mmap2[20][20];
void bfsgrass()
{
    while(!q.empty())
        q.pop();
    q.push(b);
    while(!q.empty())
    {
        xjy mid=q.front();
            q.pop();
        mmap1[mid.x][mid.y]='.';
        for(int i=0;i<4;i++)
        {
            xjy midmid;
            midmid.x=mid.x+dir[i][0];
            midmid.y=mid.y+dir[i][1];
            if( mmap1[midmid.x][midmid.y]=='#')
            {
                q.push(midmid);
            }
        }
    }
}


int bfsgrasstwo()
{
    int ans=0;
    int endans=INT_MAX;
    int endans1=INT_MAX;
    int endans2=INT_MAX;
    int minx=12,miny=12,maxx=0,maxy=0;
    while(!q.empty())
        q.pop();
    q.push(b);
    while(!q.empty())
    {
        xjy mid=q.front();
            q.pop();
        mmap2[mid.x][mid.y]='*';
        minx=min(minx,mid.x);
        maxx=max(maxx,mid.x);
        miny=min(miny,mid.y);
        maxy=max(maxy,mid.y);
        for(int i=0;i<4;i++)
        {
            xjy midmid;
            midmid.x=mid.x+dir[i][0];
            midmid.y=mid.y+dir[i][1];
            if( mmap2[midmid.x][midmid.y]=='#')
            {
                q.push(midmid);
            }
        }
    }
    for(int ii=minx;ii<=maxx;ii++)
        for(int jj=miny;jj<=maxy;jj++)
            if(mmap2[ii][jj]=='*')
            {
                xjy mid1;
                xjy mid2;
                mid1.x=ii;
                mid1.y=jj;
                int book[20][20];
                for(int iii=0;iii<20;iii++)
                {
                    for(int jjj=0;jjj<20;jjj++)
                        {
                            book[iii][jjj]=INT_MAX;
                        }
                }
                    //bfs
                while(!q.empty())
                    q.pop();
                book[mid1.x][mid1.y]=0;
                q.push(mid1);
                while(!q.empty())
                {
                    xjy mid=q.front();
                    q.pop();
                    xjy midmid;
                    for(int i1=0;i1<4;i1++)
                    {
                    midmid.x=mid.x+dir[i1][0];
                    midmid.y=mid.y+dir[i1][1];
                    if(mmap2[midmid.x][midmid.y]=='*'&&book[midmid.x][midmid.y]>(book[mid.x][mid.y]+1) )
                        {
                            q.push(midmid);
                            book[midmid.x][midmid.y]=book[mid.x][mid.y]+1;
                        }
                    }
                }
                int ans=0;
                for(int iiii=1;iiii<=m;iiii++)
                {
                    for(int jjjj=1;jjjj<=k;jjjj++)
                    {
                        if(book[iiii][jjjj]!=INT_MAX)
                        {
                              ans=max(ans,book[iiii][jjjj]);
                        }
                    }
                }
                endans1=min(endans1,ans);
            }
    for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=k;j++)
            {
                    if(mmap2[i][j]=='#')
                       {
                            b.x=i;
                            b.y=j;
                            ans=0;
                            minx=12,miny=12,maxx=0,maxy=0;
                            while(!q.empty())
                                q.pop();
                            q.push(b);
                            while(!q.empty())
                            {
                                xjy mid=q.front();
                                q.pop();
                                mmap2[mid.x][mid.y]='!';
                                minx=min(minx,mid.x);
                                maxx=max(maxx,mid.x);
                                miny=min(miny,mid.y);
                                maxy=max(maxy,mid.y);
                                for(int i=0;i<4;i++)
                                {
                                    xjy midmid;
                                    midmid.x=mid.x+dir[i][0];
                                    midmid.y=mid.y+dir[i][1];
                                    if( mmap2[midmid.x][midmid.y]=='#')
                                    {
                                        q.push(midmid);
                                    }
                                }
                            }
                            for(int ii=minx;ii<=maxx;ii++)
                                for(int jj=miny;jj<=maxy;jj++)
                                    if(mmap2[ii][jj]=='!')
                                    {
                                        xjy mid1;
                                        xjy mid2;
                                        mid1.x=ii;
                                        mid1.y=jj;
                                        int book[20][20];
                                        for(int iii=0;iii<20;iii++)
                                        {
                                            for(int jjj=0;jjj<20;jjj++)
                                                {
                                                    book[iii][jjj]=INT_MAX;
                                                }
                                        }
                    //bfs
                                        while(!q.empty())
                                            q.pop();
                                        book[mid1.x][mid1.y]=0;
                                        q.push(mid1);
                                        while(!q.empty())
                                        {
                                            xjy mid=q.front();
                                            q.pop();
                                            xjy midmid;
                                            for(int i1=0;i1<4;i1++)
                                            {
                                            midmid.x=mid.x+dir[i1][0];
                                            midmid.y=mid.y+dir[i1][1];
                                            if(mmap2[midmid.x][midmid.y]=='!'&&book[midmid.x][midmid.y]>(book[mid.x][mid.y]+1) )
                                                {
                                                    q.push(midmid);
                                                    book[midmid.x][midmid.y]=book[mid.x][mid.y]+1;
                                                }
                                            }
                                        }
                                        int ans=0;
                                        for(int iiii=1;iiii<=m;iiii++)
                                        {
                                            for(int jjjj=1;jjjj<=k;jjjj++)
                                            {
                                            if(book[iiii][jjjj]!=INT_MAX)
                                                {
                                                    ans=max(ans,book[iiii][jjjj]);
                                                }
                                            }
                                        }
                                        endans2=min(endans2,ans);
                                    }
                                    endans=max(endans1,endans2);
                                    return endans;
                        }
            }
        }

    return endans1;
}
int bfsgrassone()
{
    xjy mid1;
    xjy mid2;
    int endans=INT_MAX;
    for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=k;j++)
            {
                    if(mmap2[i][j]=='#')
                        {
                            mid1.x=i,mid1.y=j;
                            for(int ii=1;ii<=m;ii++)
                                {
                                    for(int jj=1;jj<=k;jj++)
                                    {
                                            if(mmap2[ii][jj]=='#')
                                                {
                                                    mid2.x=ii,mid2.y=jj;
                                                        int book[20][20];
                                                        for(int iii=0;iii<20;iii++)
                                                            {
                                                            for(int jjj=0;jjj<20;jjj++)
                                                                {
                                                                    book[iii][jjj]=INT_MAX;
                                                                }
                                                            }
                                                            //bfs
                                                            while(!q.empty())
                                                                q.pop();
                                                            book[mid1.x][mid1.y]=0;
                                                            book[mid2.x][mid2.y]=0;
                                                            q.push(mid1);
                                                            q.push(mid2);
                                                            while(!q.empty())
                                                            {
                                                                xjy mid=q.front();
                                                                q.pop();
                                                                xjy midmid;
                                                                for(int i1=0;i1<4;i1++)
                                                                {
                                                                    midmid.x=mid.x+dir[i1][0];
                                                                    midmid.y=mid.y+dir[i1][1];
                                                                    if(mmap2[midmid.x][midmid.y]=='#'&&book[midmid.x][midmid.y]>(book[mid.x][mid.y]+1) )
                                                                    {
                                                                        q.push(midmid);
                                                                        book[midmid.x][midmid.y]=book[mid.x][mid.y]+1;
                                                                    }
                                                                }
                                                            }
                                                            int ans=0;
                                                            for(int iiii=1;iiii<=m;iiii++)
                                                            {
                                                                for(int jjjj=1;jjjj<=k;jjjj++)
                                                                {
                                                                    if(book[iiii][jjjj]!=INT_MAX)
                                                                        {
                                                                            ans=max(ans,book[iiii][jjjj]);
                                                                        }
                                                                }
                                                            }
                                                            endans=min(endans,ans);
                                                }
                                    }
                                }
                        }
            }
        }
        return endans;
}
int main()
{

    scanf("%d",&n);
    for(int step=1;step<=n;step++)
    {
        int minx,miny,maxx,maxy;
        int cnt=0;
        memset(mmap1,'.',sizeof(mmap1));
        memset(mmap2,'.',sizeof(mmap2));
        while(!q.empty())
            q.pop();
        scanf("%d%d",&m,&k);
        getchar();
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=k;j++)
            {
                    scanf("%c",&mmap1[i][j]);
                    mmap2[i][j]=mmap1[i][j];
            }getchar();
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=k;j++)
            {
                    if(mmap1[i][j]=='#')
                       {
                            b.x=i;
                            b.y=j;
                            bfsgrass();
                            cnt++;
                       }
            }
        }
        cout << "Case " << step << ": ";
        if(cnt>=3)
            cout << "-1" << endl;
        else if(cnt==2)
        {
           cout << bfsgrasstwo() << endl;
        }
        else if(cnt==1)
        {
            cout << bfsgrassone() << endl;
        }
    }


}
そしてこれは爆捜です.
    
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
char mmap[20][20];
int m,k;
int ans=0;
struct xjy
{
    int x;
    int y;
};
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int bfs(xjy mid1,xjy mid2)
{
    queue q;
    int aans=0;
    int book[20][20];
    for(int i=0;i<=11;i++)
        for(int j=0;j<=11;j++)
        {
            book[i][j]=INT_MAX;
        }
    book[mid1.x][mid1.y]=0;
    book[mid2.x][mid2.y]=0;
    while(!q.empty())
        q.pop();
    q.push(mid1);
    q.push(mid2);
    while(!q.empty())
    {
        xjy mid;
        mid=q.front();
        q.pop();
        xjy midmid;
        for(int i=0;i<4;i++)
        {
            midmid.x=mid.x+dir[i][0];
            midmid.y=mid.y+dir[i][1];
            if(book[midmid.x][midmid.y]>(book[mid.x][mid.y]+1)&&mmap[midmid.x][midmid.y]=='#')
            {
                book[midmid.x][midmid.y]=book[mid.x][mid.y]+1;
                q.push(midmid);
            }
        }
    }

    for(int i=1;i<=m;i++)
        for(int j=1;j<=k;j++)
    {
        if(mmap[i][j]=='#')
            aans=max(aans,book[i][j]);
    }
    return aans;
}



int main()
{
    int n=0;
    scanf("%d",&n);
    for(int step=1;step<=n;step++)
    {
        ans=INT_MAX;
        memset(mmap,'.',sizeof(mmap));
        scanf("%d%d",&m,&k);
        for(int i=1;i<=m;i++)
                for(int j=1;j<=k;j++)
                    {
                        scanf(" %c",&mmap[i][j]);
                    }
            for(int i1=1;i1<=m;i1++)
                for(int j1=1;j1<=k;j1++)
                    if(mmap[i1][j1]=='#')
                    {
                        for(int i2=1;i2<=m;i2++)
                            for(int j2=1;j2<=k;j2++)
                                if(mmap[i2][j2]=='#')
                                {
                                    xjy mid1;
                                    xjy mid2;
                                    mid1.x=i1;
                                    mid2.x=i2;
                                    mid1.y=j1;
                                    mid2.y=j2;
                                    ans=min(ans,bfs(mid1,mid2));
                                }
                    }
            cout  << "Case " << step << ": " ;
            if(ans!=INT_MAX)
                cout  << ans <
django 1.10.3 userena使用
python 3異常処理(一)