P1825 [USACO11OPEN]Corn Maze S 题解

这道题就是一道普通的搜索题，非常非常普通，普通的不能再普通那种，和以前的bfs一样，不过这个bfs要注意一个特判，当弹出的那个元素的是大写字母的时候，要窜梭到对应的大写字母，并且穿梭到了另外一个大写字母以后要将其标记为true，以为之前我们是入队才标记为true，但是这里我们只要一遇到大写字母就要穿越（也就是一遇到大写字母就要改变其坐标，到另一个大写字母的坐标），其他的和一般的搜索题都一样，这大概是假的小绿，下面是AC代码，欢迎大佬前来拍砖

#include <iostream>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
void go_another(int &x,int &y,char t);
void bfs();
#define  Max 666
char g[Max][Max];
char pos[5][3]={{0,0,0},{0,-1,0},{0,0,1},{0,1,0},{0,0,-1}};
bool flag[Max][Max];
int N,M;
pair<int ,int > beg;
pair<int ,int > en;
struct Node
{
    int x,y,step;
};
    int main()
    {

        memset(flag, false, sizeof(flag));
        cin>>N>>M;//N行M列
        for(int i=1;i<=N;i++)
        {

            for(int j=1;j<=M;j++)
            {
                cin>>g[i][j];
                if(g[i][j]=='@')
                {
                    beg.first=i;
                    beg.second=j;
                }
                if(g[i][j]=='=')
                {
                    en.first=i;
                    en.second=j;
                }
            }
        }
        bfs();
        return 0;
    }


    void bfs()
    {
        Node node;
        node.x=beg.first;
        node.y=beg.second;
        flag[beg.first][beg.second]=true;
        node.step=0;
        queue<Node > que;
        que.push(node);
        while(!que.empty())
        {
            Node temp=que.front();
            que.pop();
            if(temp.x==en.first&&temp.y==en.second)
            {
                cout<<temp.step;
                return ;
            }
            if(g[temp.x][temp.y]>='A'&&g[temp.x][temp.y]<='Z')
            {
                go_another(temp.x,temp.y,g[temp.x][temp.y]);

            }

            for(int i=1;i<=4;i++)
            {
                int nx=temp.x+pos[i][1];
                int ny=temp.y+pos[i][2];
                if(nx>=1&&nx<=N&&ny>=1&&ny<=M&&g[nx][ny]!='#'&&!flag[nx][ny])
                {
                    node.x=nx;
                    node.y=ny;
                    node.step=temp.step+1;
                    que.push(node);
                    flag[nx][ny]=true;
                }
            }

        }

    }


    void go_another(int &x,int &y,char t)
    {
        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=M;j++)
            {
                if(g[i][j]==t&&(x!=i||y!=j))
                {
                    x=i;
                    y=j;
                    return ;
                }
            }
        }
    }