题解：P12684 【MX-J15-T4】叉叉学习魔法

先考虑第一问怎么求，我们将斜着的边权设为

0

，直着的边权设为

1

，那么相当于一个最短路问题，而且边权只有

0

和

1

，可以通过 01bfs 来解决。当然，我们其实不需要把图建出来，直接在矩阵上做也可以。

然后我们来考虑怎么做第二问，第二问要求魔法使用最少，乍一看可以用类似的方法，但是这问有一个前提条件——要在使用最少步数的情况下。那么这个时候可以理解为不是所有的路都能走了，我们需要知道什么情况下这条边能走。

如果我们设

dis_{i,j}

表示从起点到

(i,j)

位置的最小步数，那么对于周围的

8

个格子中能走的格子之一

(p,q)

，只有

dis_{p,q}=dis_{i,j}+w

（其中如果为直边

w=1

，否则为

0

）的时候

(i,j)

到

(p,q)

的边才是能用的。这是因为如果我们走了

dis_{p,q}<dis_{i,j}+w

的边，那么这条边会使得我们的步数不是最小的（因为存在另一种到

(p,q)

的方式步数严格小于这种方式）。所以我们设置只有这样的边能走，并把直边设为

0

，斜边设为

1

，再做一遍 01bfs 即可。

时间复杂度：

O(nm)

。

CPP

#include<bits/stdc++.h>
#define N 5005
#define pi pair<int,int>
using namespace std;
int n,m,w[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
int sx,sy,tx,ty,dis[N][N],g[N][N];
bool vis[N][N];
char a[N][N];
deque<pi>q;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>a[i][j];
			if(a[i][j]=='X')sx=i,sy=j;
			if(a[i][j]=='W')tx=i,ty=j;
		}
	}
	memset(dis,0x3f,sizeof(dis));dis[sx][sy]=0;
	q.push_front({sx,sy});
	while(!q.empty()){
		pi c=q.front();q.pop_front();
		int x=c.first,y=c.second;
		if(vis[x][y])continue;
		vis[x][y]=1;
		//cout<<x<<" "<<y<<" "<<dis[x][y]<<'\n';
		for(int i=0;i<8;++i){
			int px=x+w[i][0],py=y+w[i][1];
			if(px>=1&&px<=n&&py>=1&&py<=m&&a[px][py]!='#'){
				if(dis[px][py]>dis[x][y]+(i<4)){
					dis[px][py]=dis[x][y]+(i<4);
					if(i<4)q.push_back({px,py});
					else q.push_front({px,py});
				}
			}
		}
	}
	if(!vis[tx][ty])return cout<<"-1 -1",0;
//for(int i=1;i<=n;++i){
	//	for(int j=1;j<=m;++j)cout<<dis[i][j]<<" ";cout<<'\n';
	//}
	cout<<dis[tx][ty]<<" ";
	memset(g,0x3f,sizeof(g));g[sx][sy]=0;
	memset(vis,0,sizeof(vis));
	q.push_front({sx,sy});
	while(!q.empty()){
		pi c=q.front();q.pop_front();
		int x=c.first,y=c.second;
		if(vis[x][y])continue;
		vis[x][y]=1;
		for(int i=0;i<8;++i){
			int px=x+w[i][0],py=y+w[i][1];
			if(px>=1&&px<=n&&py>=1&&py<=m&&a[px][py]!='#'&&dis[px][py]==dis[x][y]+(i<4)){
				if(g[px][py]>g[x][y]+(i>=4)){
					g[px][py]=g[x][y]+(i>=4);
					if(i>=4)q.push_back({px,py});
					else q.push_front({px,py});
				}
			}
		}
	}
	cout<<g[tx][ty];
	return 0;
}

题解：P12684 【MX-J15-T4】叉叉学习魔法

文章操作

相关推荐

评论

题解：P12684 【MX-J15-T4】叉叉学习魔法