【每日一题】 最长距离 题解

Description

windy有一块矩形土地，被分为 N*M 块 1*1 的小格子。 有的格子含有障碍物。
如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。
如果从格子A不可以走到格子B，就没有距离。
如果格子X和格子Y有公共边，并且X和Y均不含有障碍物，就可以从X走到Y。
如果windy可以移走T块障碍物，求所有格子间的最大距离。 保证移走T块障碍物以后，至少有一个格子不含有障碍物。

Solution

数据范围很小，考虑在矩阵上进行搜索。对于每个点，找到所有可达且合法的位置(途中障碍物需要 <= T)的位置，对距离逐一验证即可。
难点在于如何将矩阵上的点映射到一维空间中。其次，在dfs的过程中需要保证最终得到的必须是最短路径长度。最后在最短路里取最大值即可。

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e6 + 5;
int n, m, T, up;
int maze[1005];
bool vis[1005];
int dist[1005];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
ll ans = 0;
void dfs(int id, int sum) {
  if(sum > T) return ;
  if(sum >= dist[id]) return ;
  dist[id] = sum;
  int x = id / m, y = id % m;
  for(int i = 0; i < 4; i++) {
    int xx = x + dir[i][0], yy = y + dir[i][1];
    int id = xx * m + yy;
    if(xx >= 0 && xx < n && yy >= 0 && yy < m) {
      dfs(id, sum + maze[id]);
    }
  }
}
ll cal(ll i, ll j) {
  ll x1 = i / m, y1 = i % m;
  ll x2 = j / m, y2 = j % m;
  return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}  
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> m >> T;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      char s; cin >> s;
      maze[i * m + j] = s - '0';
    }
  }
  up = (n - 1) * m + m - 1;
  for(int i = 0; i <= up; i++) {
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dfs(i, maze[i]);
    for(int j = 0; j <= up; j++) {
      if(dist[j] <= T) {
        ans = max(ans, cal(i, j));
      }
    }
  }
  cout << fixed << setprecision(6) << sqrt(ans) << "\n";
  return 0; 
}