【染色时间】

题目

代码

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N = 510;
int dx[] = {0,0,-1,1}, dy[] = {-1,1,0,0};
int d[N][N], w[N][N];
int n, m;
void bfs()
{
  memset(d, 0x3f, sizeof d);
  queue<PII> q;
  q.push({1,1}); d[1][1] = 0;
  while(q.size())
  {
    auto u = q.front(); q.pop();
    for(int i = 0; i < 4; i++)
    {
      int x = u.x + dx[i], y = u.y + dy[i];
      if(x < 1 || y < 1 || x > n || y > m) continue;
      if(d[x][y] > d[u.x][u.y] + w[u.x][u.y])
      {
        q.push({x,y});
        d[x][y] = d[u.x][u.y] + w[u.x][u.y];
      }
    }
  }
}
int main()
{
  cin >> n >> m;
  for(int i = 1; i <= n; i++)
  for(int j = 1; j <= m; j++)
    cin >> w[i][j];
  
  bfs();

  int ans = 0;
  for(int i = 1; i <= n; i++)
  for(int j = 1; j <= m; j++)
    ans = max(ans, d[i][j] + w[i][j]);

  cout << ans;
  return 0;
}