请求帮助
  • 板块CF254D Rats
  • 楼主Jerrlee✅
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/1/29 16:37
  • 上次更新2023/10/28 10:24:28
查看原帖
请求帮助
367652
Jerrlee✅楼主2022/1/29 16:37
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
vector<string> a,b;
struct node{
    int x,y,k;
};
vector<node> l,l1,l2;
int bfs(int x,int y){
    int cnt=0;
    queue<node> q;
    node c={x,y,k};
    q.push(c),l.push_back(c);
    while(!q.empty()){
        c=q.front();
        q.pop();
        if(a[c.x][c.y]=='R') cnt++;
        if(a[c.x][c.y]=='W') continue;
        a[c.x][c.y]='W';
        for(int i=0;i<4;i++){
            int nx=dx[i]+c.x;
            int ny=dy[i]+c.y;
            int nk=c.k-1;
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&nk>=0&&a[nx][ny]!='X'&&a[nx][ny]!='W'){
                c={nx,ny,nk};
                l.push_back(c);
                q.push(c);
            }
        }
    }
    return cnt;
}
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int r=0;
    cin>>n>>m>>k;
    a.resize(n);
    int f=1,xx=0,yy=0,xxx=0,yyy=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        for(int j=0;j<m;j++){
            r+=a[i][j]=='R';
            if(a[i][j]=='R'){
                if(f) xx=i,yy=j,f=0;
            }
        }
    }
    b=a;
    bfs(xx,yy);
    l1=l;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(a[i][j]=='R') xxx=i,yyy=j;
    bfs(xxx,yyy);
    l2=l;
    for(int i=0;i<l1.size();i++){
        a=b;
        for(int j=0;j<l2.size();j++){
            a=b;
            int r1=bfs(l1[i].x,l1[i].y),r2=bfs(l2[j].x,l2[j].y);
            if(r1==r2) return cout<<l1[i].x+1<<" "<<l1[i].y+1<<" "<<l2[j].x+1<<" "<<l2[j].y+1,0;
        }
    }
    puts("-1");
}

WA #2

2022/1/29 16:37
加载中...