题目 江湖是什么,对于在象棋界厮杀的大钉来说, 江湖就是一个矩阵,他的目标,就是在江湖之中骑着马,从他的位置出发,走到终点。
当然,大钉的马也遵从中国象棋中的“马走日”的规则, 而且在矩阵中,也会有一些障碍物,马不能跳到障碍物上;如果大钉的马面前有障碍物,即被“别马腿”, 那么他将不能跳向有障碍物的左前和右前这两个方向。
请问最少需要多少步,大钉才能骑着马跳到终点。
输入格式:
有多组测试样例。
每组第一行输入两个数 n 和 m,代表矩阵的行数和列数,2≤n≤m<100。
接下来输入 n 行字符串,其中 ‘s’ 代表起点,’e’ 代表终点,’.’ 代表空地,’#’ 代表障碍物。
输出格式:
对应每组输入,输出骑马跳到终点的最小步数,如果跳不到终点,输出 -1。
样例输入
3 3
s..
...
..e
3 3
s#.
...
# .e
样例输出
4
-1
#include<iostream>
#include<queue>
#define Min 0xfffffff
using namespace std;
class Point{
public: int x,y;
public: int step;
};
char map[100][100];
int cx[8] = {2,2,1,1,-1,-1,-2,-2};//下 下 上 上 下 下 下 下
int cy[8] = {1,-1,2,-2,2,-2,1,-1};//右 左 右 左 右 左 右 左
int minn = Min;
int n,m;
//判定条件
int check(int i,Point a,Point temp)
{
//不能越界,不能撞墙
if(temp.x >= n||temp.x < 0||temp.y < 0||temp.y >=n||map[temp.x][temp.y] == '#')
{
return 0;
}
//不能 别马腿
switch(i)
{
case 0:
case 1:return map[a.x+1][a.y] != '#';
case 2:return map[a.x][a.y+1] != '#';
case 3:return map[a.x][a.y-1] != '#';
case 4:return map[a.x][a.y+1] != '#';
case 5:return map[a.x][a.y-1] != '#';
case 6:
case 7:return map[a.x-1][a.y] != '#';
default:return 0;
}
return 1;
}
void bfs()
{
Point a,temp;
queue<Point> q;
a.x = 0;
a.y =0;
a.step = 0;
map[0][0] = '#';
q.push(a);
while(!q.empty())
{
a = q.front();
q.pop();
for(int i = 0; i < 8; i++)//广度搜索
{
temp.x = a.x + cx[i];
temp.y = a.y + cy[i];
temp.step = a.step+1;
if(check(i,a,temp))
{
if(temp.x == n-1&&temp.y == m-1)
{
if(temp.step < minn)
{
minn = temp.step;
}
continue;//防止顶点被设置为墙
}
map[temp.x][temp.y] = '#';
q.push(temp);//入对列
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n ;i++)
{
for(int j = 0; j < m; j++)
{
cin >> map[i][j];
}
}
bfs();
cout << (minn==Min?-1:minn);
return 0;
}
感觉有某个地方错了,测试的时候错了,但是对于列子是对的,大家帮忙找找。