题面node.js自带空间大常数
首先我们有一个很自然的想法，就是先从起点走到一个灌木丛，再到一个骑士处
第一步很好搞，直接队列bfs即可
第二步好像虽然边权为1，但因为起始距离不同，还是要跑最短路，感觉过不了(加上js的大常数)
于是考虑用一种奇技淫巧特殊的bfs来做
考虑一下bfs为什么是对的
其实本质上bfs的过程就是先从$dis = 0$的扩展，再扩展$dis = 1$， 再再扩展$dis = 2\cdots$
每次扩展的就是当前距离最小的，所以正确性和dijkstra一样
所以我们开$n*m$个list记下距离为i的点
然后for一遍从小到大扩展即可
js队列里记两个数MLE。。。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69const readline = require("readline");
const IO = readline.createInterface(process.stdin, process.stdout);
var n, m;
var map = [];
var nowline = 0, nowcnt = 0;
IO.on("line", function(line) {
let list = line.trim().split(' ').map(x => Number(x));
if(nowline == 0) {
nowline = 1;
m = list[0];
n = list[1];
return;
}
if(nowcnt == 0) map.push([]);
nowcnt += list.length;
for(var i of list) map[nowline - 1].push(i);
if(nowcnt == m) {
nowcnt = 0;
nowline++;
}
if(nowline == n + 1) main();
});
IO.on("close", function() {
process.exit();
});
var xy = [], dis = [];
var f;
var fx = [0, 0, -1, 1], fy = [1, -1, 0, 0];
function bfs() {
for(let i = 0; i < n * m; i++) {
for(let p of xy[i]) {
for(let j = 0; j < 4; j++) {
let newx = Math.floor(p / m) + fx[j];
let newy = p % m + fy[j];
if(newx >= 0 && newx < n && newy >= 0 && newy < m) {
if(f[map[newx][newy]] && dis[newx][newy] == -1) dis[newx][newy] = i + 1, xy[i + 1].push(newx * m + newy);
}
}
}
}
}
function main() {
for(var i = 0; i < n * m; i++) {
xy.push([]);
}
for(var i = 0; i < n; i++) {
dis.push([]);
for(var j = 0; j < m; j++) dis[i].push(map[i][j] == 2 ? (xy[0].push(i * m + j), 0) : -1);
}
f = [1, 0, 1, 0, 1];
bfs();
xy = [];
for(var i = 0; i < n * m; i++) {
xy.push([]);
}
for(var i = 0; i < n; i++) {
for(var j = 0; j < m; j++) dis[i][j] = map[i][j] == 4 && dis[i][j] != -1 ? (xy[dis[i][j]].push(i * m + j), dis[i][j]) : -1;
}
f = [1, 0, 1, 1, 1];
bfs();
let ans = n * m;
for(var i = 0; i < n; i++) {
for(var j = 0; j < m; j++) if(map[i][j] == 3 && dis[i][j] != -1 && dis[i][j] < ans) ans = dis[i][j];
}
console.log(ans);
IO.close();
}
PS: 貌似可以直接处理骑士/起点到指定灌木丛的距离