题解

紫题难点解析:看不懂英文

#include<bits/stdc++.h>
using namespace std;
struct cl{
	int vis;
	int tm;
};
struct node{
	int x;
	int y;
	int cnt;
};
int r,c,sx,sy,fx,fy;
char mp[105][105];
cl a[105][105];
int dir[4][2] = {0,1, 1,0, -1,0, 0,-1};
bool f;
int mina = 2147483646;
queue<node> q1;
void ks(){
	
	while(!q1.empty()){
		 node p = q1.front();
		 q1.pop();
		 for(int i=0;i<4;i++){
		 	int nx = p.x+dir[i][0];
		 	int ny = p.y+dir[i][1];
		 	int ns = p.cnt+1;
		 	if(nx>0&&nx<=r&&ny>0&&ny<=c&&mp[nx][ny]!='X'&&mp[nx][ny]!='D'&&a[nx][ny].vis==0){
		 		if(a[nx][ny].tm>ns||a[nx][ny].tm==0){
		 			a[nx][ny].tm = ns; 
		 			q1.push({nx,ny,ns});
				}	
				
			 }
		 }
	}
}

void bfs(int x,int y){
	queue<node> q;
	q.push({x,y,0});
	a[x][y].vis = 1;
	while(!q.empty()){
		 node p = q.front();
		 q.pop();
		 if(p.x== fx&&p.y == fy){
		 	f = 1;
		 	mina = min(mina,p.cnt);
		 	return;
		 }
		 for(int i=0;i<4;i++){
		 	int nx = p.x+dir[i][0];
		 	int ny = p.y+dir[i][1];
		 	int ns = p.cnt+1;
		 	if(nx>0&&nx<=r&&ny>0&&ny<=c&&a[nx][ny].vis == 0&&a[nx][ny].tm>ns){
		 			q.push({nx,ny,ns});
		 			a[nx][ny].vis = 1;
			 }
		 }
	}
}
int main(){
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>mp[i][j];
			if(mp[i][j] == 'S'){
				sx=i;
				sy=j;
			}
			if(mp[i][j] == 'D'){
				fx=i;
				fy =j;
			}
			if(mp[i][j] == 'X'){
				a[i][j].vis = 1;
			}
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			a[i][j].tm = 214748364;
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			if(mp[i][j]=='*'){
				a[i][j].vis = 1;
				q1.push({i,j,0});
			}
		}
	}
    ks();
	a[fx][fy].tm = 2147483646;
	bfs(sx,sy);
	if(f)cout<<mina;
	else cout<<"KAKTUS";
	return 0;
}