maze题解

我看很多大佬都是最短路做的 ，然后我最短路学的不好 ，然后偶然间看到一个大佬和我一样想法，首先直接BFS，但是这个bfs要开一个dis数组，代表该点的最短距离是多少，然后每次去更新，分别去入队每次正常走和进入传送门的，然后每次更新。

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
char cmp[350][350];
pair<int,int>pii;
int a,b,c,d;
int n,m,q;
struct node{
int x,y;
};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
vector<pair<int,int> >ans[350][350];
int dis[350][350];
void init()
{
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
    ans[i][j].clear();
}
int check(int x,int y)
{
    if(x>=0&&x<n&&y>=0&&y<m&&cmp[x][y]!='#')
        return 1;
    return 0;
}
void bfs(int a,int b)
{
    queue<node>qq;
    node s;
    s=node{a,b};
    dis[a][b]=0;
    qq.push(s);
    while(!qq.empty())
    {
        node p=qq.front();
        qq.pop();
        for(int i=0;i<4;i++)
        {
            int xx=p.x+dx[i];
            int yy=p.y+dy[i];
            if(check(xx,yy)&&dis[xx][yy]>dis[p.x][p.y]+1)
            {
                dis[xx][yy]=dis[p.x][p.y]+1;
                qq.push(node{xx,yy});
            }
        }
        for(int i=0;i<ans[p.x][p.y].size();i++)
        {
            int xx=ans[p.x][p.y][i].first;
            int yy=ans[p.x][p.y][i].second;
            if(check(xx,yy)&&dis[xx][yy]>dis[p.x][p.y]+3)
            {
                dis[xx][yy]=dis[p.x][p.y]+3;
                qq.push(node{xx,yy});
            }
        }
    }
    if(dis[c][d]!=0x3f3f3f)
        cout<<dis[c][d]<<endl;
    else
        cout<<-1<<endl;
}
int main()
{
    fio;
      while(~scanf("%d%d%d",&n,&m,&q)){
            init();
      for(int i=0;i<n;i++)
      {
          scanf("%s",cmp[i]);
      }
      for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
      {
          dis[i][j]=0x3f3f3f;
          if(cmp[i][j]=='S')
          {
              a=i,b=j;
          }
          if(cmp[i][j]=='T')
            c=i,d=j;
      }
      for(int i=1;i<=q;i++)
      {
          int x,y,xx,yy;
          scanf("%d%d%d%d",&x,&y,&xx,&yy);
          ans[x][y].push_back(make_pair(xx,yy));
      }
      bfs(a,b);
      }
    return 0;
}