福建网站制作,jsp怎么做视频网站,老王传奇新开网站,学院网站建设功能思路#xff1a;双端队列。
其实一开始你可以用BFS进行实验#xff0c;由于我们需要找最小的费用#xff0c;所以我们在BFS的时候可以这样想#xff1a;在我们遍历到第一块板子的时候#xff0c;在找周围的路时#xff0c;我们可以改成这样的判断#xff1a;如果周围的…思路双端队列。
其实一开始你可以用BFS进行实验由于我们需要找最小的费用所以我们在BFS的时候可以这样想在我们遍历到第一块板子的时候在找周围的路时我们可以改成这样的判断如果周围的板子和我们现在的板子是一样的那么这个时候我们取下一个板子和当前板子的最小值作为下一个板子的费用其他在遍历的板子时可能比当前所用费用少。可以这样想但是有一个缺点那就是当我们遍历完还要继续更新已经遍历完的格子这样是不是会造成死循环而到达不到终点呢是的如果我们标记了状态走过的格子我们已经走不了了但是走过的格子还需要进行更新所以这是矛盾的。我们需要想一种办法来解决这个问题。这就引出了这种做法就是双端队列。
我们当然是希望走到相同的板子上为好因为这样费用才能达到最少所以我们的想法就是尽可能的先走完相同的格子再去走不同的格子。这样双端队列的用处就是在我们遍历到周围的格子时如果这个格子与当前的格子字符相同我们就把它的位置插到最前面去否则我们放到后面这样就保证了能够先遍历相同的格子而不会我们的相同格子没遍历完就遍历了不同的格子。
上代码
#includeiostream
#includestdio.h
#includecstring
#includecstdlib
#includecmath
#includevector
#includealgorithm
#includestack
#includequeue
#includedeque
#include iomanip
#includesstream
#includenumeric
#includemap
#includelimits.h
#includeunordered_set
#includeset
#define int long long
#define MAX 510
#define _for(i,a,b) for(int ia;i(b);i)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef pairint, 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];
dequePIIq;
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 (cinnm,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;coutbfs(stx,sty)endl;}return 0;
}
