(计蒜客)骑马走江湖(BFS加剪枝)

àì夳堔傛蜴生んèń 2022-05-15 14:16 156阅读 0赞

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

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

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

输入格式：

有多组测试样例。

每组第一行输入两个数 nn 和 mm，代表矩阵的行数和列数

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

输出格式：

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

样例1  
输入：

3 3  
s..  
...  
..e

3 3  
s\#.  
...  
\#.e  
输出：

4  
\-1

解题思路:

把马跳的方向和可能会出现障碍物的方向先写好

int  dh[8][2] = { {-1,-2},{-1,2},{1,2},{1,-2},{2,1},{2,-1},{-2,1},{-2,-1} };
    int dht[8][2] = { {0,-1},{0,1},{0,1},{0,-1},{1,0},{1,0},{-1,0},{-1,0} };

dh表示马跳,dht表示马周围的四个方向

总体思路是利用BFS,先得出马跳的位置,然后判断是否有障碍物使马无法跳向该位置

dh和dht是对应的,一个用来移动,一个用来判断

代码:

#include <iostream>
    #include <queue>
    #include <cstring>
    using namespace std;
    
    int main() {
    	//初始化
    	int  dh[8][2] = { {-1,-2},{-1,2},{1,2},{1,-2},{2,1},{2,-1},{-2,1},{-2,-1} };
    	int dht[8][2] = { {0,-1},{0,1},{0,1},{0,-1},{1,0},{1,0},{-1,0},{-1,0} };
    
    	char nnmap[101][101];  
    	bool visited[101][101];
    	int distancemap[101][101];
    	struct pos
    	{
    		int x;
    		int y;
    	};
    
    	memset(nnmap, 0, sizeof(nnmap));
    	memset(visited, 0, sizeof(visited));
    	memset(distancemap, 0, sizeof(distancemap));
    
    	int sx = 0, sy = 0, ex = 0, ey = 0;
    	queue<pos> qque;
    	//赋值操作
    	int n, m;
    	cin >> n >> m;
    	for (int i = 0; i < n; ++i) {
    		for (int j = 0; j < m; ++j) {
    			cin >> nnmap[i][j];
    			if (nnmap[i][j] == 's') {
    				sx = i;
    				sy = j;
    			}
    
    			if (nnmap[i][j] == 'e') {
    				ex = i;
    				ey = j;
    			}
    		}
    	}
    	
    	//没有找到起点或终点
    		pos startPos{ sx,sy };
    		visited[sx][sy] = true;
    		qque.push(startPos);
    
    		while (!qque.empty()) {
    			pos currentPoint = qque.front();
    			qque.pop();
    
    			for (int i = 0; i < 8; ++i) {
    				int jumpPosX = currentPoint.x + dh[i][0];
    				int jumpPosY = currentPoint.y + dh[i][1];
    				if (jumpPosX < 0 || jumpPosX >= n || jumpPosY < 0 || jumpPosY >= m || nnmap[jumpPosX][jumpPosY] == '#') {
    					continue;
    				}
    
    				//用来判断前方是否有障碍物,如果有,则无法进行跳跃
    				int movePosX = currentPoint.x + dht[i][0];
    				int movePosY = currentPoint.y + dht[i][1];
    				if (nnmap[movePosX][movePosY] == '#') {
    					continue;
    				}
    
    				if (!visited[jumpPosX][jumpPosY]) {
    					visited[jumpPosX][jumpPosY] = true;
    					distancemap[jumpPosX][jumpPosY] = distancemap[currentPoint.x][currentPoint.y] + 1;
    					pos jp{ jumpPosX,jumpPosY };
    					qque.push(jp);
    				}
    			}
    		}
    		
    		if (distancemap[ex][ey] == 0) {
    			cout << -1 << endl;
    		}
    		else {
    			cout << distancemap[ex][ey] << endl;
    		}
    
    	system("PAUSE");
    	return 0;
    }