雪地行踪

· · 个人记录

在此鸣谢HZRdalao

题目链接

用两个队列，分别记录两种动物。

/************************************************
*Author        :  hjh179
*Created Time  :  2019.11.04.15:44
*Mail          :  [email protected]
*Problem       :  tracks
************************************************/
#include <bits/stdc++.h>
using namespace std; 
const int maxn=4000+10;
int a[maxn][maxn];
int h,w1,pos,ans;
int pre[maxn][maxn];
int dx[4]={0,0,1,-1};
int dy[4]={-1,1,0,0};
struct node{
    int x;
    int y;
};
void bfs(){
    queue<node>q1,q2;
    q2.push((node){1,1});
    int now=a[1][1];
    pre[1][1]=1;
    while(!q2.empty()){
        pos++;
        while(!q2.empty()){
            q1.push(q2.front());
            q2.pop();
        }
        while(!q1.empty()){
            int nowx=q1.front().x;
            int nowy=q1.front().y;
            ans=max(ans,pre[nowx][nowy]);
        //  cout<<nowx<<" "<<nowy<<"ans="<<ans<<endl;
            q1.pop();
            for(int i=0;i<=3;i++){
                int tx=nowx+dx[i];
                int ty=nowy+dy[i];
                if(tx==0||ty==0||tx>h||ty>w1||pre[tx][ty]<=pos||a[tx][ty]==0)continue;
                if(a[tx][ty]==now)q1.push((node){tx,ty}),pre[tx][ty]=pos;
                else if(pre[tx][ty]<=pos+1)continue;
                else q2.push((node){tx,ty}),pre[tx][ty]=pos+1;
            }
        }
        if(now==2)now=1;
        else now=2;
    }
}
int main() {
    freopen("tracks.in","r",stdin);
    freopen("tracks.out","w",stdout);
    cin>>h>>w1;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w1;j++){
            char c;
            cin>>c;
            if(c=='F')a[i][j]=1;
            if(c=='R')a[i][j]=2;
        }
    }
    memset(pre,0x3f,sizeof(pre));
    bfs();
    cout<<ans<<endl;
    return 0;
}