我的代码在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;
}