Children of the Candy Corn POJ

Children of the Candy Corn POJ - 3083 点击打开链接

题意：一个有优先级的bfs，输出三个数，先输出优先向左走的步数，然后输出优先向右走的步数，最后输出最短路。

（不过，之后看题解，大佬们都是用dfs加bfs来做，我就给出我bfs的做法，dfs+bfs的大家可以自己去搜）

思路:分三次搜索，第一次优先向左走，第二次优先向右，最后直接最短路

注意：由于前两次不一定是最短路，所以不用标记是否走过，而且，由于是有优先级，可以走的话，就必须先走优先级高的，所以，在判断cango后，如果可行，加入队列后就要break；

还有一个难点就是根据优先级搜索，这里的转向数组dx，dy，tx，ty以及搜索的顺序都需要好好推一下才能发现规律

优先左走时，优先级为，左，上，右，下。优先右走时，优先级为，右，上，左，下。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
char Map[50][50];
int ans[50][50];
int vis[50][50];
int sx,sy,ex,ey;
typedef struct man
{
    int first,second,face;
}P;
int dx[]={-1,0,1,0};//方向数组
int dy[]={0,-1,0,1};
int tx[]={0,1,0,-1};
int ty[]={-1,0,1,0};
bool cango(int x,int y,int flag)
{
    if(x<=0||x>n||y<=0||y>m||Map[x][y]=='#'||(flag==0&&vis[x][y]))
        return 0;
    return 1;
}
int bfs(int flag,int f)//flag记录优先级，1为向左走的优先级，2为向右走，0为最短路
{
    memset(ans,0,sizeof ans);
    if(flag==0){
        memset(vis,0,sizeof vis);
        vis[sx][sy]=1;
    }
    queue<P> que;
    while(!que.empty())
        que.pop();
    P p;
    p.first=sx;
    p.second=sy;
    p.face=f;
    que.push(p);
    while(!que.empty()){
        p=que.front();
        que.pop();
        int mx,my,face;
        if(p.first==ex&&p.second==ey){
            return ans[ex][ey];
        }
        if(flag==1){
            for(int i=4;i>=1;i--){
                mx=p.first+dx[(p.face+i)%4];//保证按照优先级搜索的公式，需要自己好好体会一下，在这里，我令1，2，3，4分别代表上左下右
                my=p.second+dy[(p.face+i)%4];
                face=(p.face+1+i)%4;
                if(face==0)
                    face=4;
                if(cango(mx,my,flag)){
                    ans[mx][my]=ans[p.first][p.second]+1;
                    P q;
                    q.first=mx,q.second=my,q.face=face;
                    que.push(q);
                    break;//因为有优先级，所以优先级高，并且可走的，一定要走
                }
            }
        }
        else if(flag==2){
            for(int i=1;i<=4;i++){
                mx=p.first+tx[(p.face+i)%4];
                my=p.second+ty[(p.face+i)%4];
                face=(p.face+2+i)%4;
                if(face==0)
                    face=4;
                if(cango(mx,my,flag)){
                    ans[mx][my]=ans[p.first][p.second]+1;
                    P q;
                    q.first=mx,q.second=my,q.face=face;
                    que.push(q);
                    break;
                }
            }
        }
        else if(flag==0){//迷宫最短路模板
            for(int i=0;i<4;i++){
                mx=p.first+dx[i];
                my=p.second+dy[i];
                if(cango(mx,my,flag)){
                    ans[mx][my]=ans[p.first][p.second]+1;
                    vis[mx][my]=1;
                    P q;
                    q.first=mx,q.second=my,q.face=p.face;
                    que.push(q);
                }
            }
        }
    }
}
int main()
{
    int t,face;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&m,&n);
        for(int i=1;i<=n;i++){
            getchar();
            for(int j=1;j<=m;j++){
                scanf("%c",&Map[i][j]);
                if(Map[i][j]=='S'){
                    sx=i,sy=j;
                    if(Map[i-1][j]=='.')//判断起点朝向，最后我发现不判断好像也没什么问题
                        face=1;
                    else if(Map[i][j-1]=='.')
                        face=2;
                    else if(Map[i+1][j]=='.')
                        face=3;
                    else
                        face=4;
                }
                else if(Map[i][j]=='E')
                    ex=i,ey=j;
            }
        }
        int a=bfs(1,face)+1,b=bfs(2,face)+1,c=bfs(0,face)+1;
        printf("%d %d %d
",a,b,c);
    }
    return 0;
}