19分求助Dalao
查看原帖
19分求助Dalao
210719
Violet___Evergarden楼主2021/7/24 17:39
#include<bits/stdc++.h>
using namespace std;
const int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
int n,m,qx,qy;
char mp[301][301];
struct CH
{
  int x,y;
}c[27][1];
int f[301][301],h=1,t=1,zx,zy;
struct QUE
{
  int x,y;
}q[1000001];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
  for(int j=1;j<=m;j++)
  {
    cin>>mp[i][j];
    if(mp[i][j]=='@')
    {
      qx=i,qy=j;
    }
    if(mp[i][j]=='=')
    {
        zx=i,zy=j;
    }
    if(mp[i][j]>='A'&&mp[i][j]<='Z')//记录装置的起点和终点
    {
      if(c[mp[i][j]-'A'][0].x>0&&c[mp[i][j]-'A'][0].y>0)
      {
        c[mp[i][j]-'A'][1].x=i;
        c[mp[i][j]-'A'][1].y=j;
        //cout<<1<<" "<<c[mp[i][j]-'A'][1].x<<" "<<c[mp[i][j]-'A'][1].y<<endl;
      }
      else
      {
        c[mp[i][j]-'A'][0].x=i;
        c[mp[i][j]-'A'][0].y=j;
        //cout<<2<<" "<<c[mp[i][j]-'A'][0].x<<" "<<c[mp[i][j]-'A'][0].y<<endl;
      }
    }
  }
}
q[t].x=qx,q[t].y=qy;
f[qx][qy]=1;
while(h<=t)
{
  int x1=q[h].x,y1=q[h].y;
  for(int i=1;i<=4;i++)、、四个方向扩展
  {
    int xx=x1+dx[i],yy=y1+dy[i];
    if(xx<1||xx>n||yy<1||yy>m)continue;//走出地图
    if(mp[xx][yy]=='#'||f[xx][yy]>0)continue;//不能走或走过
    f[xx][yy]=f[x1][y1]+1;//更新步数
    //cout<<xx<<" "<<yy<<" "<<f[xx][yy]<<endl;
    if(mp[xx][yy]=='=')
    {
      cout<<f[xx][yy]-1;
      return 0;
    }
    bool flag=false;
    if(mp[xx][yy]>='A'&&mp[xx][yy]<='Z')//如果走到了装置
    {
      int k=mp[xx][yy]-'A';
      if(c[k][0].x==xx&&c[k][0].y==yy)//跳点
      {
        //cout<<c[k][1].x<<" "<<c[k][1].y<<" "<<f[xx][yy]<<endl;
        f[c[k][1].x][c[k][1].y]=f[xx][yy];
        q[++t].x=c[k][1].x;
        q[t].y=c[k][1].y;
        continue;
      }
      else
      {
        //cout<<c[k][0].x<<" "<<c[k][0].y<<" "<<f[xx][yy]<<endl;
        f[c[k][0].x][c[k][0].y]=f[xx][yy];
        q[++t].x=c[k][0].x;
        q[t].y=c[k][0].y;
        continue;
      }
    }
    else//如果没走到装置,将现在的点入队就可
    {
        q[++t].x=xx;
        q[t].y=yy;
    }
  }
  h++;
}
cout<<f[zx][zy]-1;
return 0;
}
2021/7/24 17:39
加载中...