ZZULIOJ 2746: 布丁（BFS）

2746: 布丁

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N = 510;
int dir[4][2]={
    {
    -1,0},{
    0,-1},{
    1,0},{
    0,1}};
int a[N][N],dist[N][N];
int n,m;
int bfs(int dx,int dy)
{
    memset(dist,-1,sizeof dist);queue<PII>q;dist[0][0]=0;q.push({
    0,0});while(q.size()){
    PII t=q.front();q.pop();for(int i=0;i<4;i++){
    int x=t.x+dir[i][0];int y=t.y+dir[i][1];if(x<0||x>=n||y<0||y>=m) continue;if(a[x][y]==1||dist[x][y]!=-1) continue;dist[x][y]=dist[t.x][t.y]+1;if(x==dx&&y==dy) return dist[x][y];q.push({
    x,y});}}return 2e9;
}
int main()
{
    int x,y;cin>>n>>m>>x>>y;for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>a[i][j];if(x==0&&y==0) puts("布丁是笨蛋");else if(a[x][y]==1) puts("小Z果然是最菜的"); else{
    int ans1=x+y;int ans2=bfs(x,y);if(ans2<=ans1) puts("布丁是笨蛋");else puts("小Z果然是最菜的");}return 0;
}