题解：P15031 [UOI 2021 II Stage] 矩阵

kmszcll2024 · 2026-01-26 13:43:25 · 题解

此题不难。

题意

裸的广搜。输入时遇到 1 就入队，队列中存下起点和当前的坐标。按照公式计算曼哈顿距离，更新答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,mx;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct node{
    int x,y,lx,ly;
};
queue<node>q;
bool vis[25][25];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char a;
            cin>>a;
            if(a=='1'){
                vis[i][j]=1;
                q.push({i,j,i,j});
            }
        }
    }
    while(!q.empty()){
        auto [x,y,lx,ly]=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int dx=x+dir[i][0],dy=y+dir[i][1];
            if(dx<1||dy<1||dx>n||dy>m||vis[dx][dy])continue;
            vis[dx][dy]=1;
            mx=max(mx,abs(dx-lx)+abs(dy-ly));
            q.push({dx,dy,lx,ly});
        }
    }
    printf("%d",mx);
    return 0;
}