洛谷 P4554 小明的游戏

思路：双端队列。

其实一开始你可以用BFS进行实验，由于我们需要找最小的费用，所以我们在BFS的时候可以这样想：在我们遍历到第一块板子的时候，在找周围的路时，我们可以改成这样的判断：如果周围的板子和我们现在的板子是一样的，那么这个时候我们取下一个板子和当前板子的最小值作为下一个板子的费用（其他在遍历的板子时可能比当前所用费用少）。可以这样想，但是有一个缺点，那就是当我们遍历完还要继续更新已经遍历完的格子，这样是不是会造成死循环而到达不到终点呢？是的，如果我们标记了状态，走过的格子我们已经走不了了；但是走过的格子还需要进行更新，所以这是矛盾的。我们需要想一种办法来解决这个问题。这就引出了这种做法，就是双端队列。

我们当然是希望走到相同的板子上为好，因为这样费用才能达到最少，所以，我们的想法就是尽可能的先走完相同的格子，再去走不同的格子。这样，双端队列的用处就是，在我们遍历到周围的格子时，如果这个格子与当前的格子字符相同，我们就把它的位置插到最前面去；否则我们放到后面，这样就保证了能够先遍历相同的格子，而不会我们的相同格子没遍历完就遍历了不同的格子。

上代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<unordered_set>
#include<set>
#define int long long
#define MAX 510
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef pair<int, int> PII;
int n, m;
int counts;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
char maps[MAX][MAX];
int dist[MAX][MAX];
deque<PII>q;
int stx, sty, edx, edy;
int bfs(int x, int y) {q.push_back({ x,y });dist[x][y] = 0;while (!q.empty()) {auto tmp = q.front();q.pop_front();char ch = maps[tmp.first][tmp.second];_for(i, 0, 4) {int a = dx[i] + tmp.first;int b = dy[i] + tmp.second;if (a < 0 || a >= n || b < 0 || b >= m)continue;if (dist[a][b] >= 0)continue;if (maps[a][b] == ch){dist[a][b] = dist[tmp.first][tmp.second];q.push_front({ a,b });}if (maps[a][b] != ch) {dist[a][b] = dist[tmp.first][tmp.second] + 1;q.push_back({ a,b });}if (a == edx && b == edy) {return dist[a][b];}}}return -1;
}
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);while (cin>>n>>m,n||m) {_for(i, 0, n) {_for(j, 0, m)cin >> maps[i][j];}memset(dist, -1, sizeof dist);q.clear();cin >> stx >> sty >> edx >> edy;cout<<bfs(stx,sty)<<endl;}return 0;
}