开头的注释不用管，自己瞎写的
by 一只书虫仔 @ 2021-10-05 14:52:26
我觉得用爆搜好一点，就是从右上角开始往外扩散，知道走到左下角，记录一下花费，然后回溯，最后取一下最小值应该就行了（很慢吧。。）
by int4096 @ 2021-10-05 18:39:01
@[一只书虫仔](/user/114914)
by int4096 @ 2021-10-05 18:39:19
@[int4096](/user/542452) 哥哥，我就用的爆搜
by 一只书虫仔 @ 2021-10-05 18:50:07
最短路？很像。。~~别问，问就是不知道~~
by int4096 @ 2021-10-05 18:54:42
您 dfs 函数咋这么长啊（
by int64 @ 2021-10-05 19:00:22
```cpp
void dfs(int x, int y, int cost, bool f) { //x,y 不解释,cost 是当前花费，f表示上一步是否更改了颜色
if (x < 1 || x > m || y < 1 || y > m) { //在地图外面
return;
}
if (cost >= ans[x][y]) { //剪枝
return;
}
ans[x][y] = cost; //更新当前答案。因为前面 cost 如果 >= ans[x][y] 的时候已经退出了，所以这里 ans[x][y] 肯定取的是最小值
if (x == m && y == m) { //到达终点，更新答案，退出
res = min(res, cost);
return;
}
for (int i = 0;i < 4;i++) {
int xx = x + dx[i]; //接下来搜索(xx,yy)
int yy = y + dy[i];
if (map[xx][yy] != 0) { //如果当前不是空白的
if (map[xx][yy] == map[x][y]) {
dfs(xx, yy, cost, 0); //颜色一致，无消耗
} else {
dfs(xx, yy, cost + 1, 0); //颜色不一致，增加一个消耗
}
} else if (!f) {
map[xx][yy] = map[x][y]; //更新无色的地方为当前颜色
dfs(xx, yy, cost + 2, 1); //花费2
map[xx][yy] = 0; //走过之后颜色恢复
}
}
}
```
by int64 @ 2021-10-05 19:03:34
@[一只书虫仔](/user/114914) 大概就这样，有问题请指出（
by int64 @ 2021-10-05 19:03:58
这里剪枝一定要写 `cost >= ans[x][y]` 不然会死循环，因为我没有添加 vis 数组（
~~其实我是忘了加了，后来模拟赛结束以后，我自己检查我代码的时候发现了。但竟然 A 了（~~
by int64 @ 2021-10-05 19:07:51
@[int4096](/user/542452) 牛逼了，您说爆搜是最短路
by 一只书虫仔 @ 2021-10-05 19:12:08