[数据结构与算法]AcWing 188 武士风度的牛 题解（BFS）

AcWing 188 武士风度的牛
BFS简单应用，注意马走日就行了

#include<bits/stdc++.h>

using namespace std;

const int N = 200, M = N * N; 

#define x first
#define y second

typedef pair<int, int>PII;

int n;
int c, r;
char g[N][N];
PII q[M];
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int ans;
bool st[N][N];
int dis[N][N];
int a1, a2;

void bfs(int sx, int sy){
	st[sx][sy] = true;
	q[0] = {sx, sy};
	int hh = 0, tt = 0;
	
	//cout<<"----"<<endl;
	
	while(hh <= tt){
		auto t = q[hh ++ ];
		for(int i = 0; i < 8; i ++ ){
			int xx = t.x + dx[i], yy = t.y + dy[i];
			if(xx < 0 || xx >= r || yy < 0 || yy >= c || st[xx][yy] || g[xx][yy] == '*'){
				continue;
			}
			if(g[xx][yy] == 'H'){
				dis[xx][yy] = min(dis[xx][yy], dis[t.x][t.y] + 1);
				continue;
			}
		//	cout<<xx<<' '<<yy<<' '<<dis[xx][yy]<<endl;
			dis[xx][yy] = dis[t.x][t.y] + 1;
			q[ ++ tt] = {xx, yy};
			st[xx][yy] = 1;
		}
	}
}

int main()
{
	cin>>c>>r;
	memset(dis, 0x3f, sizeof dis);
	for(int i = 0; i < r; i ++ ){
		for(int j = 0; j < c; j ++ ){
			cin>>g[i][j];
			if(g[i][j] == 'H'){
				a1 = i, a2 = j;
			}		
		}
	}
	
	for(int i = 0; i < r; i ++ ){
		for(int j = 0; j < c; j ++ ){
			if(g[i][j] == 'K'){
				dis[i][j] = 0;
				bfs(i, j);
			} 
		}
	}
		
	cout<<dis[a1][a2]<<endl;
	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖