大钉骑马走江湖（bfs）

╰+攻爆jí腚メ 2022-10-01 01:48 144阅读 0赞

江湖是什么，对于在象棋界厮杀的大钉来说，江湖就是一个矩阵，他的目标，就是在江湖之中骑着马，从他的位置出发，走到终点。

当然，大钉的马也遵从中国象棋中的“马走日”的规则，而且在矩阵中，也会有一些障碍物，马不能跳到障碍物上；如果大钉的马面前有障碍物，即被“别马腿”，那么他将不能跳向有障碍物的左前和右前这两个方向。

请问最少需要多少步，大钉才能骑着马跳到终点。

输入格式：

有多组测试样例。

每组第一行输入两个数 n*n* 和 m*m*，代表矩阵的行数和列数，2 \\leq n \\leq m < 1002≤*n*≤*m*<100。

接下来输入 n*n* 行字符串，其中 's' 代表起点，'e' 代表终点，'.' 代表空地，'\#' 代表障碍物。

输出格式：

对应每组输入，输出骑马跳到终点的最小步数，如果跳不到终点，输出 \-1−1。

#### 样例输入 ####

3 3
    s..
    ...
    ..e
    
    3 3
    s#.
    ...
    #.e

#### 样例输出 ####

4
    -1

思路：

挡住马脚的情况不走，然后就按日的方式跳

代码：

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<string.h>
    #include<queue>
    using namespace std;
    int dir[8][2]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};
    int dir2[4][2]={-1,0,0,1,1,0,0,-1};
    char map[101][101];
    int n,m,cnt;
    struct st{
    	int x,y,c;
    };
    queue <struct st> Q;
    int check(int x,struct st s)
    {
    	int xx,yy;
    	switch(x) //如果大钉的马面前有障碍物返回真 
    	{
    		case 0:
    		case 7:
    			xx = s.x+dir2[0][0];
    			yy = s.y+dir2[0][1];
    			if (xx<0||yy<0||xx>=n||yy>=m||map[xx][yy]=='#')
    			  return 1;
    			return 0;
    		case 1:
    		case 2:
    			xx = s.x+dir2[1][0];
    			yy = s.y+dir2[1][1];
    			if (xx<0||yy<0||xx>=n||yy>=m||map[xx][yy]=='#')
    			  return 1;
    			return 0;
    		case 3:
    		case 4:
    			xx = s.x+dir2[2][0];
    			yy = s.y+dir2[2][1];
    			if (xx<0||yy<0||xx>=n||yy>=m||map[xx][yy]=='#')
    			  return 1;
    			return 0;
    		case 5:
    		case 6:
    			xx = s.x+dir2[3][0];
    			yy = s.y+dir2[3][1];
    			if (xx<0||yy<0||xx>=n||yy>=m||map[xx][yy]=='#')
    			  return 1;
    			  return 0;
    	}
    }
    int bfs(struct st s, struct st e)
    {
    	int i,j,xx,yy,flag,v[101][101]={0};
    	struct st temp;
    	s.c = 0;
    	Q.push(s);
    	v[s.x][s.y] = 1;
    	while (!Q.empty())
    	{
    		s = Q.front();
    		Q.pop();
    		if (s.x == e.x && s.y ==e.y)
    		 return s.c;
    		for (i=0; i<8; i++)
    		{
    			if (check(i,s))
    			{
    				continue;
    			}
    			temp.x = s.x + dir[i][0];
    			temp.y = s.y + dir[i][1];
    			if (temp.x<0||temp.y<0||temp.x>=n||temp.y>=m||map[temp.x][temp.y]=='#'||v[temp.x][temp.y])
    			 continue;
    			temp.c = s.c+1;
    			v[temp.x][temp.y] = 1;
    			Q.push(temp);
    		}
    	}
    	return -1;
    }
    int main()
    {
    	int i,j;
    	struct st s,e;
    	while (cin>>n>>m)
    	{
    		getchar();
    		cnt = -1;
    		memset(map,0,sizeof(map));
    		while (!Q.empty())
    		{
    			Q.pop();
    		}
    		for (i=0; i<n; i++)
    		{
    			for (j=0; j<m; j++)
    			{
    				cin>>map[i][j];
    				if (map[i][j]=='s')
    				{
    					s.x = i;
    					s.y = j;
    				}
    				if (map[i][j] == 'e')
    				{
    					e.x = i;
    					e.y = j;
    				}
    			}
    		}
    		cnt = bfs(s,e);
    		cout<<cnt<<endl;
    	}
    	return 0;
    }