pjT3翻车了，怕是连pj组都不如
这道题一看上去就是用bfs的啊，用dfs还怕爆栈。
然后就手动地打了个非常暴力的bfs，只拿到了25pts。
翻了题解才知道这个东西居然还能用spfa！
总结性话语：搜索题不会做的，试着转换成图论题，用图论题的思路解决暴力模拟也许会更方便。
所以我们可以类似于spfa，建立一个vis数组和dist数组。
如何记录状态？
当前行列肯定要记的，然后就要考虑那个花两块钱变色的东西。
不难发现再开一维记录当前位置的颜色即可，不需要去更改原矩阵。当原颜色与当前颜色不一样的时候就说明我使用了膜法。
有一个贪心的做法：当我下一步是一个无颜色的格子，那么最优的是直接指定为同样颜色，这样只要花两块钱，不然要花三块钱。
对于不同的颜色，注意去分别判断，用类似于spfa的方法去更新。
所以就完事了。最后输出一下std::min(dist[n][n][0], dist[n][n][1])就可以了。
代码：
#include#include #include const int maxn = 105;const int dx[] = {0, 0, 1, -1};const int dy[] = {1, -1, 0, 0};struct Nodes{ int x, y, col; Nodes(int x, int y, int col):x(x), y(y), col(col){}};int G[maxn][maxn];int dist[maxn][maxn][2];bool vis[maxn][maxn][2];int n, m;int main(){ memset(dist, 0x3f, sizeof dist); memset(G, -1, sizeof G); scanf("%d%d", &n, &m); while(m--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); G[x][y] = z; } std::queue q; dist[1][1][G[1][1]] = 0; q.push(Nodes(1, 1, G[1][1])); vis[1][1][G[1][1]] = true; while(!q.empty()) { Nodes u = q.front(); q.pop(); int x = u.x, y = u.y, col = u.col, res = dist[x][y][col]; vis[x][y][col] = false; for(int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if(nx >= 1 && nx <= n && ny >= 1 && ny <= n) { if(G[nx][ny] == -1) { if(G[x][y] == -1) continue; if(res + 2 < dist[nx][ny][col]) { dist[nx][ny][col] = res + 2; if(!vis[nx][ny][col]) { q.push(Nodes(nx, ny, col)); vis[nx][ny][col] = true; } } } else if(G[nx][ny] != col) { if(res + 1 < dist[nx][ny][G[nx][ny]]) { dist[nx][ny][G[nx][ny]] = res + 1; if(!vis[nx][ny][G[nx][ny]]) { q.push(Nodes(nx, ny, G[nx][ny])); vis[nx][ny][G[nx][ny]] = true; } } } else if(G[nx][ny] == col) { if(res < dist[nx][ny][G[nx][ny]]) { dist[nx][ny][G[nx][ny]] = res; if(!vis[nx][ny][G[nx][ny]]) { q.push(Nodes(nx, ny, G[nx][ny])); vis[nx][ny][G[nx][ny]] = true; } } } } } } int ans; if(G[n][n] != -1) ans = dist[n][n][G[n][n]]; else ans = std::min(dist[n][n][0], dist[n][n][1]); if(ans != 0x3f3f3f3f) printf("%d\n", ans); else printf("-1\n"); return 0;}