链接
题意
n*m中有p个type，经过了任意一个 type=i 的各自才能打开 type=i+1 的钥匙，最初有type=1的钥匙, 问拿到type=p的钥匙最少需要走多少步
思路
第一想法就是按type来递推, 将type相同的存到一起，dp[i][j]=min(dp[i][j], dp[k][l]+distance([i][j], [k][l]))，其中 a[i][j] = a[k][l]+1. 但这样type相同的个数较多时就超时了，所以根据type的个数，较多时使用BFS就可以了。 我没有仔细研究时间复杂度就过了，官方题解好像有均摊复杂度的证明。
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <string>
#define LL long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define MOD 1000000007
using namespace std;
struct POS{
int x, y;
POS(int x = 0, int y = 0) :x(x), y(y){};
};
vector<POS> s[90005];
int a[305][305];
int d[305][305];
bool vis[305][305];
int dp[305][305];
const int step[4][2] = { 1, 0, 0, 1, -1, 0, 0, -1 };
int get_distance(POS &a, POS &b){
return abs(a.x - b.x) + abs(a.y - b.y);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
int n, m, p;
while (~scanf("%d%d%d", &n, &m, &p)){
int x;
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
scanf("%d", &a[i][j]);
s[a[i][j]].push_back(POS(i, j));
}
}
memset(dp, INF, sizeof(dp));
for (int i = 0; i < s[1].size(); ++i){
dp[s[1][i].x][s[1][i].y] = s[1][i].x + s[1][i].y - 2;
}
for (int i = 2; i <= p; ++i){
if (s[i].size() * s[i - 1].size() < n * m){
for (int j = 0; j < s[i].size(); ++j){
POS J = s[i][j];
for (int k = 0; k < s[i - 1].size(); ++k){
POS K = s[i - 1][k];
dp[J.x][J.y] = min(dp[K.x][K.y] + get_distance(J, K), dp[J.x][J.y]);
}
}
}
else{
memset(d, INF, sizeof(d));
memset(vis, 0, sizeof(vis));
queue<POS> Q;
for (int j = 0; j < s[i - 1].size(); ++j){
POS J = s[i - 1][j];
Q.push(J);
vis[J.x][J.y] = true;
d[J.x][J.y] = dp[J.x][J.y];
}
while (!Q.empty()){
POS u = Q.front();
Q.pop();
vis[u.x][u.y] = false;
for (int j = 0; j < 4; ++j){
int x = u.x + step[j][0];
int y = u.y + step[j][1];
if (a[u.x][u.y] == i) dp[u.x][u.y] = min(dp[u.x][u.y], d[u.x][u.y]);
if (x < 1 || x > n || y < 1 || y > m) continue;
if (d[x][y] > d[u.x][u.y] + 1){
d[x][y] = d[u.x][u.y] + 1;
if (!vis[x][y]){
vis[x][y] = true;
if (a[x][y] == i){
dp[x][y] = min(dp[x][y], d[x][y]);
}
Q.push(POS(x, y));
}
}
}
}
}
}
POS K = s[p][0];
cout << dp[K.x][K.y] << endl;
}
}