求助,莫名RE
  • 板块CF254D Rats
  • 楼主_8762
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/6/25 09:20
  • 上次更新2023/10/27 22:38:30
查看原帖
求助,莫名RE
370829
_8762楼主2022/6/25 09:20

我的代码在CF上运行RE,但本地和洛谷在线IDE都能运行

RE数据:

4 4 1 XXXX XR.X X.RX XXXX

我的代码:

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
//#define int long long
//#pragma GCC optimize("Ofast")
#define Pii pair<int,int>
#define f first
#define s second
using namespace std;
const int N=1e3+5;
vector<Pii> pos[9],Rats;
int n,m,d,cnt,R[N][N];
bool b[N][N],v[N][N];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
void pre()
{
  for(int i=1;i<=8;++i)
    for(int x=-i;x<=i;++x)
      for(int y=-i;y<=i;++y)
        if(abs(x)+abs(y)<=i)pos[i].push_back({x,y});
  cin>>n>>m>>d;
  for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
      {
        char x;cin>>x;
        if(x=='X')b[i][j]=1; if(x=='R')Rats.push_back({i,j}),R[i][j]=1;
      }
}
void Ex1(int x,int y,int d)
{
  queue<Pii> q; q.push({x,y}); v[x][y]=1;
  if(R[x][y])R[x][y]=2,++cnt;
  for(int i=1;i<=d;++i)
    {
      int siz=q.size();
      for(int j=1;j<=siz;++j)
        {
          auto k=q.front(); q.pop();
          for(int p=0;p<4;++p)
            {
              int nx=k.f+dx[p],ny=k.s+dy[p];
              if(nx<=0||ny<=0||nx>n||ny>m)continue;
              if(v[nx][ny]||b[nx][ny])continue;
              v[nx][ny]=1; if(R[nx][ny])R[nx][ny]=2,++cnt; q.push({nx,ny});
            }
        }
    }
  for(auto i:pos[d])
    {
      int xx=x+i.f,yy=y+i.s;
      if(xx>n||xx<=0||yy<=0||yy>m)continue; 
      if(v[xx][yy])v[xx][yy]=0;
    }
}
int Ex2(int x,int y,int d)
{
  int res=0;
  queue<Pii> q; q.push({x,y}); v[x][y]=1; if(R[x][y]==1)++res;
  for(int i=1;i<=d;++i)
    {
      int siz=q.size();
      for(int j=1;j<=siz;++j)
        {
          auto k=q.front(); q.pop();
          for(int p=0;p<4;++p)
            {
              int nx=k.f+dx[p],ny=k.s+dy[p];
              if(nx<=0||ny<=0||nx>n||ny>m)continue;
              if(v[nx][ny]||b[nx][ny])continue;
              v[nx][ny]=1; if(R[nx][ny]==1)++res; q.push({nx,ny});
            }
        }
    }
  for(auto i:pos[d])
    {
      int xx=x+i.f,yy=y+i.s;
      if(xx>n||xx<=0||yy<=0||yy>m)continue;
      if(v[xx][yy])v[xx][yy]=0;
    }
  return res;
}
signed main()
{
  ios::sync_with_stdio(0),cin.tie(0); pre();
  int xx=Rats[0].f,yy=Rats[0].s;//Rat1
  for(auto k:pos[d])//boom1
    {
      int fx=xx+k.f,fy=yy+k.s;//pos boom1
      if(fx>n||fx<=0||fy<=0||fy>m)continue; if(b[fx][fy])continue;
      cnt=0; Ex1(fx,fy,d); int x,y;

      if(cnt==Rats.size()){cout<<"2 1 "<<fx<<" "<<fy<<'\n'; return 0;}
      for(auto i:Rats)if(R[i.f][i.s]==1){x=i.f,y=i.s;break;}//Rat2
      
      for(auto k2:pos[d])//boom2
        {
          int nx=x+k2.f,ny=y+k2.s;//pos boom2
          if(nx>n||nx<=0||ny<=0||ny>m)continue; if(b[nx][ny])continue;
          if(cnt+Ex2(nx,ny,d)==Rats.size()){cout<<fx<<" "<<fy<<" "<<nx<<" "<<ny<<'\n'; return 0;}
        }
      for(auto i:pos[d])
        {
          int nx=xx+i.f,ny=yy+i.s;
          if(nx>n||nx<=0||ny<=0||ny>m)continue;
          if(R[nx][ny]==2)R[nx][ny]=1;
        }
    }
  cout<<"-1"<<'\n'; return 0;
}

2022/6/25 09:20
加载中...