1416: 【作】【提高】骑士牛

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：5 解决：4

题目描述

John用他的一头母牛和Don先生交换了一头“骑士牛”。这头牛有一个独特的能力——在牧场中能像中国象棋中的马一样跑跳（会中国象棋吗？不会？注意：本题不考虑马被“蹩脚”的情况）。当然，这头牛不能跳到岩石或树上，不过能跳到有牧草的地方。这儿有一个宽为X，高为Y的矩形牧场(1 ≤ X ≤ 150; 1 ≤ Y ≤ 150)。 “骑士牛”和其它牛一样喜欢干草。给你一张包含“骑士牛”出发地和树、岩石、灌木或其它障碍物及大包干草等位置信息的地图，确定“骑士牛”得到干草最少要跳几“跳”。地图中“骑士牛”出发地用'K'表示；障碍物用'*'表示，牧草用'.'表示，干草所在地用'H'表示。这儿有一个示例地图：
j=1 j=2 j=3 j=4 j=5 j=6 j=7 j=8 j=9 j=10
i=1 . . . . . . . . . .
i=2 . . . . * . . . . .
i=3 . . . . . . . . . .
i=4 . . . * . * . . . .
i=5 . . . . . . . * . .
i=6 . . * . . * . . . H
i=7 * . . . . . . . . .
i=8 . . . * . . . * . .
i=9 . K . . . . . . . .
i=10 . . . * . . . . . *
i=11 . . * . . . . * . .

骑士牛得到干草的最少步骤在下图中用ABC……表示，最少要跳5“跳”（其它的路径可能超过5“跳”）：
j=1 j=2 j=3 j=4 j=5 j=6 j=7 j=8 j=9 j=10
i=1 . . . . . . . . . .
i=2 . . . . * . . . . .
i=3 . . . . . . . . . .
i=4 . . . * . * . . . .
i=5 . . . . . . . * . .
i=6 . . * . . * . . . HF
i=7 * . .B . . . . . . .
i=8 . . . * .C . . * .E .
i=9 . KA . . . . .D . . .
i=10 . . . * . . . . . *
i=11 . . * . . . . * . .

输入

第1行: 两个空格隔开的整数: X 和 Y
第2..Y+1行: 第Y-i+2行包含X个没有空格的字符（就像上面的地图一样）：表示第i行的地图。

输出

第1行: 一个单独的整数表示最少的得到干草的“跳”数。所有的数据都能得到干草。

样例输入 复制 

10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..

样例输出 复制 

5

提示

#include<bits/stdc++.h>
using namespace std;
#define N 110
char a[N][N];
int d[N][N];
int n,m;
int dx[9]={0,1,1,2,-2,-2,2,-1,-1};
int dy[9]={0,2,-2,1,1,-1,-1,-2,2};
int sx,sy,ex,ey;
void dfs(int x,int y,int dep){
	d[x][y]=dep;
	int tx,ty;
	for(int i=1;i<=8;i++){
		tx=x+dx[i];
		ty=y+dy[i];
		if(d[tx][ty]>dep+1&&(a[tx][ty]=='.'||a[tx][ty]=='H')){
			dfs(tx,ty,dep+1);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			if(a[i][j]=='K'){
				sx=i;
				sy=j;
			} 
			else if(a[i][j]=='H'){
				ex=i;
				ey=j;
			}
			d[i][j]=INT_MAX;
		}
	}
	dfs(sx,sy,0);
	cout<<d[ex][ey];
	return 0;
}

来源/分类

提交提交记录统计露一手!