考虑每次更新就跑一遍 bfs。
\(O(n^4)\),复杂度不对?
但是注意到 \(dis\) 的最大值也就是 \(n\),每次更新 \(dis\) 至少减一。
所以最大值最多被更新 \(n\) 次,一共更新 \(O(n^3)\) 次,复杂度是对的。
直接暴力。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define eb emplace_back
const int N = 505;
int a[N][N], dis[N][N], n;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
void upd(int x, int y)
{
deque<pair<int, int>> q;
q.eb(x, y);
while(q.size())
{
auto [x, y] = q.front(); q.pop_front();
for(int o = 0; o < 4; o ++)
{
int u = x + dx[o], v = y + dy[o];
if(u > 0 && v > 0 && u <= n && v <= n && dis[u][v] > dis[x][y] + a[u][v])
{
dis[u][v] = dis[x][y] + a[u][v];
if(a[u][v]) q.eb(u, v);
else q.push_front({u, v});
}
}
}
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
a[i][j] = 1;
memset(dis, 0x3f, sizeof dis);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
dis[i][j] = min(min(i, j), min(n - i + 1, n - j + 1));
ll ans = 0;
for(int i = 1; i <= n * n; i ++)
{
int k; cin >> k;
int x = (k - 1) / n + 1, y = (k - 1) % n + 1;
a[x][y] = 0, dis[x][y] --;
ans += dis[x][y];
upd(x, y);
}
cout << ans;
return 0;
}
标签:int,题解,更新,eb,AGC044B,front,dis
From: https://www.cnblogs.com/adam01/p/18340191