0%

[洛谷 P4554] 小明的游戏

题目

给出一个 $n \times m$ 的棋盘,每次可以向上下左右移动一格,如果格子相同,费用为 $0$,不然为 $1$,问从 $(a, b)$ 走到 $(x, y)$ 的最小花费。$1 \le n, m \le 500$。

思路

最开始想用 dfs 跑过去…然后理所当然的超时了。

然后开始写 djikstra,写着写着感觉就写成广搜了。

不懂为什么那么多人总要写 spfa,dijkstra 也不长啊?

然后这道题的点是从 $0$ 开始标号的,跟某比赛卡行末空格一样毒瘤。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

struct Node {
int x, y, dis;
friend bool operator < (const Node &a, const Node &b) {
return a.dis > b.dis;
}
} ;

int dis[510][510], g[510][510];
int n, m, sx, sy, ex, ey;
char a[510][510];
bool vis[510][510];

inline int dist(int ax, int ay, int bx, int by) {
return a[ax][ay] != a[bx][by];
}

void dijkstra() {
memset(dis, 0x3f3f3f3f, sizeof(dis));
memset(vis, false, sizeof(vis));
dis[sx][sy] = 0;
std::priority_queue<Node> q;
q.push((Node){sx, sy, 0});
while (!q.empty()) {
Node top = q.top();
q.pop();
if (vis[top.x][top.y]) continue;
vis[top.x][top.y] = true;
for (int i = 0; i < 4; ++i) {
int nx = top.x + dx[i], ny = top.y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && dis[nx][ny] > dis[top.x][top.y] + dist(top.x, top.y, nx, ny)) {
dis[nx][ny] = dis[top.x][top.y] + dist(top.x, top.y, nx, ny);
q.push((Node){nx, ny, dis[nx][ny]});
}
}
}
}

int main() {
while (std::cin >> n >> m && n + m) {
for (int i = 1; i <= n; ++i) scanf("%s", a[i] + 1);
read(sx), read(sy), read(ex), read(ey);
++sx, ++sy, ++ex, ++ey;
dijkstra();
printf("%d\n", dis[ex][ey]);
}
return 0;
}