WA25分求差错or小数据Hack
查看原帖
WA25分求差错or小数据Hack
288716
lzqy_楼主2020/8/19 19:30

rt,样例过了


//这两个数组用来存储一对传送装置
#include <bits/stdc++.h>
using namespace std;
int a[1001][1001],n,m;
int p[4][2]= {{1,0},{-1,0},{0,-1},{0,1}};
double cnt=1;
struct str
{
  int x,y;
} M;
str pp[1001],ppp[1001];//这两个数组用来存储一对传送装置
queue<str>q;
bool k[1001][1001];
int BFS()
{
  int ans=0,len;
  str t;
  q.push(M);
  k[M.x][M.y]=1;
  while(!q.empty())
  {
    len=q.size();
    ans++;
    for(int i=1; i<=len; i++)
    {
      t=q.front(),q.pop();
      if(a[t.x][t.y]==10)
        return ans-1;
      for(int i=0; i<4; i++)
      {
        int xx=t.x+p[i][0],yy=t.y+p[i][1];
        if(xx>n||xx<1||yy>m||yy<1||k[xx][yy]==1||a[xx][yy]==0)
          continue;
        if(a[xx][yy]==1)
          q.push({xx,yy}),k[xx][yy]=1;
        else//传送情况
        {
          str tt;
          if(pp[a[xx][yy]-100].x==xx&&pp[a[xx][yy]-100].y==yy)
            tt=ppp[a[xx][yy]-100];
          else
            tt=pp[a[xx][yy]-100];
          q.push({xx,yy});//传过去穿回来
          k[xx][yy]=1;
          if(k[tt.x][tt.y]==0)//传过去
            q.push(tt),k[tt.x][tt.y]=1;

        }
      }
    }
  }
  return 0;
}
int main()
{
  char c;
  cin>>n>>m;
  for(int i=1; i<=n; i++)
    for(int j=1; j<=m; j++)
    {
      cin>>c;
      if(c=='#')
        a[i][j]=0;
      else if(c=='.')
        a[i][j]=1;
      else if(c=='=')
        a[i][j]=10;
      else if(c=='@')
        a[i][j]=1,M.x=i,M.y=j;
      else
      {
        a[i][j]=(int)cnt+100;//加一百特判
        if((int)cnt==(double)cnt)
        //判断是第一次出现的传送还是第二次
          pp[(int)cnt]= {i,j};
        else
          ppp[(int)cnt]= {i,j};
        cnt+=0.5;

      }
    }
  cout<<BFS();
  return 0;
}
2020/8/19 19:30
加载中...