AtCoder Beginner Contest 176 D - Wizard in Maze (BFS,双端队列)

题意 :给你一张图,"."表示能走,"#表示不能走,步行可以向四周四个方向移动一个单位,使用魔法可以移动到周围\(5\)Ｘ\(5\)的空地,问能否从起点都早终点,并求最少使用多少次魔法.

题解 :明显是用BFS,但是我们要能步行就步行,尽量少使用魔法,所以我们可以用deque来存状态,将步行的状态放在前面,魔法的放在后面,这样就能保证优先步行,用结构体来表示状态即可.

代码 :

struct misaka{

	int x,y;

	int cnt;

}e;

int n,m;

int sx,sy;

int ex,ey;

char g[2000][2000];

bool st[2000][2000];

int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

int ans=INF;

void bfs(){

	deque<misaka> q;

	q.pb({sx,sy,0});

	while(!q.empty()){

		auto tmp=q.front();

		q.pop_front();

		int x=tmp.x;

		int y=tmp.y;

		int cnt=tmp.cnt;

		if(x==ex && y==ey){

			ans=cnt;

			return;

		}

		if(st[x][y]) continue;

		st[x][y]=true;

		for(int i=0;i<4;++i){

			int tx=x+dx[i];

			int ty=y+dy[i];

			if(tx<1 || tx>n || ty<1 || ty>m  || g[tx][ty]=='#') continue;

			q.pf({tx,ty,cnt});

		}

		for(int i=x-2;i<=x+2;++i){

			for(int j=y-2;j<=y+2;++j){

				if(i<1 || i>n || j<1 || j>m  || g[i][j]=='#') continue;

				q.pb({i,j,cnt+1});

			}

		}

	}

}

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	n=read();

	m=read();

	sx=read();

	sy=read();

	ex=read();

	ey=read();

	for(int i=1;i<=n;++i){

		scanf("%s",g[i]+1);

	}

	bfs();

	if(ans==INF) puts("-1");

	else printf("%d\n",ans);

    return 0;

}