P4162 解题报告
题意
给你一张 \(n \times m\) 的图,其中 \(a_{i,j}=1\) 表示有障碍,否则没有障碍,其中可以消除 \(t\) 个障碍,求所有格子的最大距离。
分析
这其实就是一道搜索的版子题。
根据数据范围很容易想到可以枚举起点,然后通过广搜遍历起点到每一个点的距离和需要消除障碍的个数。遍历完之后枚举终点,求出消除障碍个数小于 \(t\) 的节点距离起点的最大的距离。
注意,在求最大距离的时候不要先开方,保持精度,等到输出的时候再开方。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int n, m, s, dis[105][105], a[105][105];
double maxn;
struct node{int x, y;};
void bfs(int x, int y){//搜索版子
queue<node> q;
q.push((node){x, y});
dis[x][y] = a[x][y];
while (!q.empty()){
node t = q.front();
q.pop();
for (int i = 0; i < 4; i++){
int nx = t.x + dx[i], ny = t.y + dy[i];
if (nx > 0 && nx <= n && ny > 0 && ny <= m && dis[nx][ny] > dis[t.x][t.y] + (a[nx][ny] == 1)){
dis[nx][ny] = dis[t.x][t.y] + (a[nx][ny] == 1);//记录需要消除的障碍个数
q.push((node){nx, ny});
}
}
}
}
signed main(){
scanf("%lld%lld%lld", &n, &m, &s);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++) scanf("%1lld", &a[i][j]);//这样可以直接一位一位输入整数
}
memset(dis, 0x3f, sizeof dis);
bfs(1, 1);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){//枚举起点
memset(dis, 0x3f, sizeof dis);
bfs(i, j);//遍历到每个节点的距离
for (int k = 1; k <= n; k++){
for (int l = 1; l <= m; l++){//枚举终点
if (dis[k][l] <= s) maxn = max(maxn, (double)(k - i) * (k - i) + (l - j) * (l - j));
}
}
}
}
printf("%.6lf", sqrt(maxn));
return 0;
}
标签:node,报告,int,nx,ny,解题,P4162,105,dis
From: https://www.cnblogs.com/ccf-ioi/p/17871556.html