题解 | TheChivalrousCow-牛客假日团队赛

题目描述

Farmer John traded one of his cows for a cow that Farmer Don called 'The Knight'. This cow has the unique ability to jump around the pasture in moves that looked like a knight on a chessboard (two squares over, one up... or maybe two squares down and one over, etc.). 'The Knight' can't jump on rocks or trees, but can really make her way around the pasture, which is partitioned for our purposes into an X by Y set of squares (1 <= X <= 150; 1 <= Y <= 150). 'The Knight' likes hay just like any other cow. Given a map of 'The Knight's starting place, locations of the tree, shrub, rock, and other obstacles, and the location of a bale of hay, determine how many 'hops' the Knight must make in order to get to the hay. The Knight cow will be marked by a 'K' on the map; obstacles by '*', and the haybale by 'H'. Here's a typical map:
11 | . . . . . . . . . .
10 | . . . . * . . . . .
9 | . . . . . . . . . .
8 | . . . * . * . . . .
7 | . . . . . . . * . .
6 | . . * . . * . . . H
5 | * . . . . . . . . .
4 | . . . * . . . * . .
3 | . K . . . . . . . .
2 | . . . * . . . . . *
1 | . . * . . . . * . .
0 ----------------------
                               1
0 1 2 3 4 5 6 7 8 9 0

 The knight could travel the path indicated by A, B, C, ... to get to the hay bale in just 5 moves (other routes of length 5 might be possible):
11 | . . . . . . . . . .
10 | . . . . * . . . . .
9 | . . . . . . . . . .
8 | . . . * . * . . . .
7 | . . . . . . . * . .
6 | . . * . . * . . . F<
5 | * . B . . . . . . .
4 | . . . * C . . * E .
3 | .>A . . . . D . . .
2 | . . . * . . . . . *
1 | . . * . . . . * . .
0 ----------------------
                               1
0 1 2 3 4 5 6 7 8 9 0
Hint: This problem is probably most easily solved with a simple first-in/first-out 'queue' data structure implemented as a few parallel arrays.

5

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct node {
	int x,y,step;
};
int dir[][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
const int maxn = 155;
char dot[maxn][maxn];
int vis[maxn][maxn];
int ans = 0,x,y;
int main(void) {
	void BFS(int start_x,int start_y) ;
	int start_x,start_y;
	scanf("%d%d",&y,&x);
	getchar();                                     // 输入的时候注意把缓存区内存留的换行符号用getchar()吸收掉
	memset(dot,0,sizeof(dot));
	memset(vis,0,sizeof(vis));
	for(int i = 1; i <= x; i ++) {
		for(int j = 0; j <= y ; j ++) {            // 输入每行字符的时候也要注意
			scanf("%c",&dot[i][j]);
			if(dot[i][j] == 'K') {
				start_x = i;
				start_y = j;
			}
		}
	}
	ans = 0;
	BFS(start_x,start_y);
	printf("%d\n",ans);
	return 0;
}
void BFS(int start_x,int start_y) {
	queue<node>que;
	while(!que.empty()) que.pop();
	node first,second;
	first.x = start_x,first.y = start_y,first.step = 0;
	vis[start_x][start_y] = 1;
	que.push(first);
	while(!que.empty()) {
		first = que.front();
		que.pop();
		if(dot[first.x][first.y] == 'H') {
			ans = first.step;
			return ;
		}
		for(int i = 0; i < 8; i ++) {
			second = first;
			second.x = first.x + dir[i][0];
			second.y = first.y + dir[i][1];

			if(second.x < 1 || second.y < 1 || second.x > x || second.y > y || vis[second.x][second.y] || dot[second.x][second.y] == '*') continue;
			second.step = first.step + 1;
			vis[second.x][second.y] = 1;
			que.push(second);
		}
	}
	return ;
}