先考虑第一问怎么求，我们将斜着的边权设为 $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)$。

#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;
}