AtCoder Beginner Contest 176 D-Wizard in Maze
题意
给出一个高为 n，宽为 m 的迷宫，给出起点和终点，有两种走路方式：
- 向上下左右四个方向移动一格
- 用掉一点魔法值，在以当前点为中心的 5 * 5 的格子中，移向任意一个格子
问最少用多少魔法值可以走到终点？
思路
刚开始直接写暴力 bfs，1，2两种方式一起用，T了。
然后就写了一个广搜+并查集+最短路，给俺恶心死了。
看到有好多人在很短的时间就过掉了，看他们的代码用的是双端队列。
so 学习了一下。
我们肯定是尽可能的先用第一种方式，当无法走到的时候，再用魔法。
使用双端队列，进行 bfs，通过第一种方式走到的往队列头放，通过第二种方式走到的往队列尾放。
代码
/*
* @Autor: valk
* @Date: 2020-08-11 12:38:37
* @LastEditTime: 2020-09-28 17:19:07
* @Description: 如果邪恶 是华丽残酷的乐章 它的终场 我会亲手写上 晨曦的光 风干最后一行忧伤 黑色的墨 染上安详
*/
#include <algorithm>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int seed = 12289;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int N = 1e3 + 10;
int mov[4][2]={0,1,0,-1,-1,0,1,0};
char str[N][N];
int vis[N][N];
struct note
{
int x,y,cnt;
};
void solve()
{
int n,m,ax,ay,ex,ey;
scanf("%d%d%d%d%d%d",&n,&m,&ax,&ay,&ex,&ey);
for(int i=1;i<=n;i++){
scanf("%s",str[i]+1);
}
deque<note>q;
q.push_front({ax,ay,0});
memset(vis,inf,sizeof(vis));
int ans=-1;
vis[ax][ay]=1;
while(!q.empty()){
note now=q.front();
q.pop_front();
if(now.x==ex&&now.y==ey){
ans=now.cnt;
break;
}
for(int i=0;i<4;i++){
note next = {now.x+mov[i][0],now.y+mov[i][1],now.cnt};
if(next.x<1||next.x>n||next.y<1||next.y>m||next.cnt>=vis[next.x][next.y]||(str[next.x][next.y]=='#')) continue;
vis[next.x][next.y]=next.cnt;
q.push_front(next);
}
int temp=now.cnt+1;
for(int i=max(1,now.x-2);i<=min(n,now.x+2);i++){
for(int j=max(1,now.y-2);j<=min(m,now.y+2);j++){
if((vis[i][j]>temp)&&(str[i][j]!='#')){
q.push_back({i,j,temp});
vis[i][j]=temp;
}
}
}
}
printf("%d
",ans);
}
int main()
{
solve();
return 0;
}