求助!BFS有一个测试点不过

P2385 [USACO07FEB] Bronze Lilypad Pond B

sky_233 @ 2024-03-30 10:59:04

#include<bits/stdc++.h>
using namespace std;
int n,m,m1,m2;
int ex,ey;
int mm[31][31];
bool st[31][31];
int dist[31][31];
typedef pair<int,int>PII;
queue<PII>q;
int bfs(int x,int y){
    int ws1[8] = {-m2,-m1,m1,m2,m2,m1,-m1,-m2};
    int ad1[8] = {m1,m2,m2,m1,-m1,-m2,-m2,-m1};
    q.push({x,y});
    while(!q.empty()){
        PII s = q.front();
        q.pop();
        if(s.first==ex&&s.second==ey)return dist[s.first][s.second];
        for(int i=0;i<8;i++){
            int za = s.first+ws1[i];
            int zb = s.second+ad1[i];
            if(za<1||za>n||zb<1||zb>m)continue;
            if(st[za][zb]==true||mm[za][zb]==2||mm[za][zb]==3)continue;
            st[za][zb] = true;
            q.push({za,zb});
            dist[za][zb] = dist[s.first][s.second]+1;
        }
    }
}
int main(){
    cin>>n>>m>>m1>>m2;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mm[i][j];
            if(mm[i][j]==4){
                ex=i;
                ey=j;   
            }
        }
    }
    int res;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mm[i][j]==3){
                st[i][j] = true;
                res = bfs(i,j);
                break;
            }
        }
    }cout<<res;
    return 0;
} 

by wangruiqi36 @ 2024-03-30 11:42:35

if(st[za][zb]==true||mm[za][zb]==2||mm[za][zb]==3)continue;

改成

if(st[za][zb]==true||mm[za][zb]==2||mm[za][zb]==0)continue;

|