Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

感觉写这种题是要折寿的

Posted by tjrac6016203284 at 2018-10-03 20:20:53 on Problem 1475
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<cstdio>
#include<queue>
#include<stack>
using namespace std;

char graph[30][30];
int n,m;
struct node
{
    int step_B,step_S,sx,sy,bx,by;
};
node flag[30][30][30][30];
node temp,temp_1;

struct coor
{
    int x,y;
};
coor S,B,T;

void init()
{
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<m; ++j)
        {
            cin>>graph[i][j];
            if(graph[i][j]=='S')
            {
                S.x=i;
                S.y=j;
            }
            else if(graph[i][j]=='B')
            {
                B.x=i;
                B.y=j;
            }
            else if(graph[i][j]=='T')
            {
                T.x=i;
                T.y=j;
            }
        }
    }
    for(int sx=0; sx<n; ++sx)
    {
        for(int sy=0; sy<m; ++sy)
        {
            for(int bx=0; bx<n; ++bx)
            {
                for(int by=0; by<m; ++by)
                {
                    flag[sx][sy][bx][by].step_B=-1;
                    flag[sx][sy][bx][by].step_S=-1;
                }
            }
        }
    }
}
int dx[4]= {0,0,1,-1};
int dy[4]= {1,-1,0,0};

void bfs()
{
    queue<node>Q;
    flag[S.x][S.y][B.x][B.y].step_B=0;
    flag[S.x][S.y][B.x][B.y].step_S=0;
    flag[S.x][S.y][B.x][B.y].sx=-1;
    flag[S.x][S.y][B.x][B.y].sy=-1;
    flag[S.x][S.y][B.x][B.y].bx=-1;
    flag[S.x][S.y][B.x][B.y].by=-1;
    temp.step_S=0;
    temp.step_B=0;
    temp.sx=S.x;
    temp.sy=S.y;
    temp.bx=B.x;
    temp.by=B.y;
    Q.push(temp);
    while(!Q.empty())
    {
        temp=Q.front();
       // printf("%d %d %d %d \n",temp.sx,temp.sy,temp.bx,temp.by);
        Q.pop();
        for(int i=0; i<4; ++i)
        {
            temp_1=temp;
            temp_1.step_S=temp.step_S+1;
            temp_1.sx=temp_1.sx+dx[i];
            temp_1.sy=temp_1.sy+dy[i];

            if(temp_1.sx==temp_1.bx&&temp_1.sy==temp_1.by)
            {
                temp_1.bx=temp_1.bx+dx[i];
                temp_1.by=temp_1.by+dy[i];
                temp_1.step_B=temp_1.step_B+1;
            }
            if(graph[temp_1.sx][temp_1.sy]=='#'||graph[temp_1.bx][temp_1.by]=='#'||temp_1.sx<0||temp_1.sx>=n||temp_1.bx<0||temp_1.bx>=n||   temp_1.sy<0||temp_1.sy>=m||temp_1.by<0||temp_1.by>=m)
            {
                continue;
            }



            if(flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_S==-1||flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_S>temp.step_S+1)
            {
                if(flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_B==-1||flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_B>=temp.step_B+1)
                {
                    flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by]=temp;
                    flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_S=temp.step_S+1;
                    flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_B=temp.step_B+1;
                    Q.push(temp_1);
                }
            }
            if(flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_B>temp.step_B+1)
            {
                flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by]=temp;
                flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_S=temp.step_S+1;
                flag[temp_1.sx][temp_1.sy][temp_1.bx][temp_1.by].step_B=temp.step_B+1;
                Q.push(temp_1);
            }


        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int ctor=1;

    while(cin>>n>>m)
    {
        if(n+m==0)
            break;

        init();
        cout<<"Maze #"<<ctor++<<endl;
       // cout<<"*************"<<endl;
        bfs();
        int SX,SY,BX,BY,ans_B=100000,ans_S=100000;


        for(int sx=0; sx<n; ++sx)
        {
            for(int sy=0; sy<m; ++sy)
            {
                if(flag[sx][sy][T.x][T.y].step_B!=-1&&flag[sx][sy][T.x][T.y].step_S!=-1)
                if(flag[sx][sy][T.x][T.y].step_B<ans_B||(flag[sx][sy][T.x][T.y].step_B==ans_B&&flag[sx][sy][T.x][T.y].step_S<ans_S))
                {

                    ans_B=flag[sx][sy][T.x][T.y].step_B;
                    ans_S=flag[sx][sy][T.x][T.y].step_S;
                   // cout<<ans_B<<endl;
                    SX=sx;
                    SY=sy;
                    BX=T.x;
                    BY=T.y;
                }
            }
        }
        if(ans_B==100000)
        {
            cout<<"Impossible."<<endl;
        }
        else
        {
            stack<node>SS;
            temp.sx=SX;
            temp.sy=SY;
            temp.bx=BX;
            temp.by=BY;

            while(flag[temp.sx][temp.sy][temp.bx][temp.by].step_S>0)
            {
                SS.push(temp);
                temp=flag[temp.sx][temp.sy][temp.bx][temp.by];
            }
          //  cout<<flag[temp.sx][temp.sy][temp.bx][temp.by].step_S<<endl;
            temp.sx=S.x;
            temp.sy=S.y;
            temp.bx=B.x;
            temp.by=B.y;


            while(!SS.empty())
            {
                temp_1=SS.top();
                SS.pop();
                char c;
                int x,y;
                x=temp_1.sx-temp.sx;
                y=temp_1.sy-temp.sy;
                if(x==0&&y==1)
                    c='e';
                else if(x==0&&y==-1)
                    c='w';
                else if(x==1&&y==0)
                    c='s';
                else if(x==-1&&y==0)
                    c='n';

                if(temp_1.bx!=temp.bx||temp_1.by!=temp.by)
                    c=c-32;
                cout<<c;
               // printf("(%d,%d)->(%d,%d) :%c\n",temp.sx,temp.sy,temp_1.sx,temp_1.sy,c);
                temp=temp_1;
            }
            cout<<endl;


        }
        cout<<endl;
        //printf("Ans= %d\n",ans);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator