(200分)- 跳马Java JS Python C题目描述马是象棋包括中国象棋和国际象棋中的棋子走法是每步直一格再斜一格即先横着或者直者走一格然后再斜着走一个对角线可进可退可越过河界俗称马走日字。给定 m 行 n 列的棋盘网格图棋盘上只有棋子象棋中的棋子“马”并且每个棋子有等级之分等级为 k 的马可以跳 1~k 步走的方式与象棋中“马”的规则一样不可以超出棋盘位置问是否能将所有马跳到同一位置如果存在输出最少需要的总步数每匹马的步数相加不存在则输出-1。注允许不同的马在跳的过程中跳到同一位置坐标为x,y的马跳一次可以跳到的坐标为(x1, y2)(x1, y-2)(x2, y1)(x2, y-1)(x-1, y2)(x-1, y-2)(x-2, y1)(x-2, y-1)的格点上但是不可以超出棋盘范围。输入描述第一行输入mn代表 m 行 n 列的网格图棋盘1 ≤ m, n ≤ 25接下来输入 m 行 n 列的网格图棋盘如果第 i 行第 j 列的元素为 . 代表此格点没有棋子如果为数字 k1 ≤ k ≤ 9代表此格点存在等级为 k 的“马”输出描述输出最少需要的总步数每匹马的步数相加不存在则输出-1。用例输入3 2..2...输出0说明只有一匹马不需要跳动输入3 547.484744.7....输出17说明无题目解析题目要求我们找到一个满足以下条件的位置所有马都能到达该位置所有马到达该位置的总步数最小返回这个最小总步数每个马有等级K限制了它能跳的最大步数。解题思路对每匹马进行BFS遍历记录它能到达的位置及对应步数维护所有马都能到达的公共位置集合计算每个公共位置的总步数找出最小值具体实现定义stepMap矩阵记录各位置的总步数使用reach集合维护公共可达位置初始为全棋盘对每匹马执行以下操作使用BFS遍历可达位置记录首次到达各位置的步数更新stepMap中对应位置的总步数更新reach集合为当前马可达位置与前序reach的交集最终检查若reach为空则返回-1否则在reach中找出stepMap值最小的位置关键点使用BFS确保记录的是最小步数通过集合交逐步缩小公共位置范围最终只需遍历reach集合即可找到最优解JS算法源码const rl require(readline).createInterface({ input: process.stdin }); var iter rl[Symbol.asyncIterator](); const readline async () (await iter.next()).value; void (async function () { // 棋盘行数, 棋盘列数 const [m, n] (await readline()).split( ).map(Number); // 记录所有马都可达的公共位置坐标 const reach new Set(); // 棋盘矩阵 const map []; for (let i 0; i m; i) { map.push(await readline()); // 初始时假设所有位置都是各个马可达的 for (let j 0; j n; j) { reach.add(i * n j); // 二维坐标一维化 } } // 最小步数和矩阵stepMap[i][j]记录各个马走到棋盘(i,j)位置的最小步数之和 const stepMap new Array(m).fill(0).map(() new Array(n).fill(0)); function getResult() { // 遍历棋盘 for (let i 0; i m; i) { for (let j 0; j n; j) { // 如果棋盘(i,j)位置是马 if (map[i][j] ! .) { // 马的等级 const k parseInt(map[i][j]); // 对该马进行BFS走日 bfs(i, j, k); } } } // 如果所有马走完发现没有公共可达位置 if (reach.size 0) { return -1; } // 记录所有马都可达位置的最小步数和 let minStep Infinity; for (let pos of reach) { const y pos % n; const x (pos - y) / n; // (x,y)是所有马都可达的位置stepMap[x][y]记录所有马到达此位置的步数和 minStep Math.min(minStep, stepMap[x][y]); } return minStep; } // 马走日的偏移量 const offsets [ [1, 2], [1, -2], [2, 1], [2, -1], [-1, 2], [-1, -2], [-2, 1], [-2, -1], ]; // 广搜 function bfs(sx, sy, k) { // 广搜队列 // (sx,sy)为马所在初始位置马到达初始位置需要0步 let queue [[sx, sy, 0]]; // 记录该马可以访问(sx,sy)位置 const vis new Set(); vis.add(sx * n sy); // 二维坐标一维化 // k记录该马剩余可走步数 while (queue.length 0 k 0) { // newQueue记录该马花费相同步数的可达的位置即BFS按层遍历的层 const newQueue []; // 按层BFS for (let [x, y, step] of queue) { for (let [offsetX, offsetY] of offsets) { // 马走日到达的新位置 const newX x offsetX; const newY y offsetY; const pos newX * n newY; // 如果新位置越界或者已访问过则不能访问 if (newX 0 || newX m || newY 0 || newY n || vis.has(pos)) continue; // 将新位置加入新层 newQueue.push([newX, newY, step 1]); // 该马到达(newX, newY)位置最小步数为step1, 由于该马首次到达(newX, newY)位置因此step1就是最小步数 stepMap[newX][newY] step 1; // 记录该马访问过该位置后续如果该马再次访问该位置则不是最小步数 vis.add(pos); } } queue newQueue; k--; // 剩余步数减1 } // BFS完后将公共可达位置reach和当前马可达位置取交集交集部分就是新的公共可达位置 reach.forEach((pos) { if (!vis.has(pos)) { reach.delete(pos); } }); } console.log(getResult()); })();Java算法源码import java.util.HashSet; import java.util.LinkedList; import java.util.Scanner; public class Main { // 棋盘行数 static int m; // 棋盘列数 static int n; // 棋盘矩阵 static char[][] map; // 最小步数和矩阵stepMap[i][j]记录各个马走到棋盘(i,j)位置的最小步数之和 static int[][] stepMap; // 记录所有马都可达的公共位置坐标 static HashSetInteger reach; // 马走日的偏移量 static int[][] offsets {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}}; public static void main(String[] args) { Scanner sc new Scanner(System.in); m sc.nextInt(); n sc.nextInt(); map new char[m][n]; stepMap new int[m][n]; reach new HashSet(); for (int i 0; i m; i) { map[i] sc.next().toCharArray(); // 初始时假设所有位置都是各个马可达的 for (int j 0; j n; j) { reach.add(i * n j); } } System.out.println(getResult()); } public static int getResult() { // 遍历棋盘 for (int i 0; i m; i) { for (int j 0; j n; j) { // 如果棋盘(i,j)位置是马 if (map[i][j] ! .) { // 马的等级 int k map[i][j] - 0; // 对该马进行BFS走日 bfs(i, j, k); } } } // 如果所有马走完发现没有公共可达位置 if (reach.size() 0) { return -1; } // 记录所有马都可达位置的最小步数和 int minStep Integer.MAX_VALUE; for (int pos : reach) { int x pos / n; int y pos % n; // (x,y)是所有马都可达的位置stepMap[x][y]记录所有马到达此位置的步数和 minStep Math.min(minStep, stepMap[x][y]); } return minStep; } // 广搜 public static void bfs(int sx, int sy, int k) { // 广搜队列 LinkedListint[] queue new LinkedList(); // (sx,sy)为马所在初始位置马到达初始位置需要0步 queue.add(new int[] {sx, sy, 0}); // 记录该马可以访问(sx,sy)位置 HashSetInteger vis new HashSet(); vis.add(sx * n sy); // 二维坐标一维化 // k记录该马剩余可走步数 while (queue.size() 0 k 0) { // newQueue记录该马花费相同步数的可达的位置即BFS按层遍历的层 LinkedListint[] newQueue new LinkedList(); // 按层BFS for (int[] tmp : queue) { // 当前马所在位置(x,y)以及马到达该位置的步数step int x tmp[0]; int y tmp[1]; int step tmp[2]; for (int[] offset : offsets) { // 马走日到达的新位置 int newX x offset[0]; int newY y offset[1]; int pos newX * n newY; // 如果新位置越界或者已访问过则不能访问 if (newX 0 || newX m || newY 0 || newY n || vis.contains(pos)) continue; // 将新位置加入新层 newQueue.add(new int[] {newX, newY, step 1}); // 该马到达(newX, newY)位置最小步数为step1, 由于该马首次到达(newX, newY)位置因此step1就是最小步数 stepMap[newX][newY] step 1; // 记录该马访问过该位置后续如果该马再次访问该位置则不是最小步数 vis.add(pos); } } queue newQueue; k--; // 剩余步数减1 } // BFS完后将公共可达位置reach和当前马可达位置取交集交集部分就是新的公共可达位置 reach.retainAll(vis); } }Python算法源码import sys # 输入获取 m, n map(int, input().split()) # 棋盘行数, 棋盘列数 grid [input() for _ in range(m)] # 棋盘矩阵 stepGrid [[0] * n for _ in range(m)] # 最小步数和矩阵stepMap[i][j]记录各个马走到棋盘(i,j)位置的最小步数之和 # 记录所有马都可达的公共位置坐标 reach set() for i in range(m): for j in range(n): reach.add(i * n j) # 马走日的偏移量 offsets ((1, 2), (1, -2), (2, 1), (2, -1), (-1, 2), (-1, -2), (-2, 1), (-2, -1)) # 广搜 def bfs(sx, sy, k): global reach # 广搜队列 # (sx,sy)为马所在初始位置马到达初始位置需要0步 queue [(sx, sy, 0)] # 记录该马可以访问(sx,sy)位置 vis set() vis.add(sx * n sy) # 二维坐标一维化 # k记录该马剩余可走步数 while len(queue) 0 and k 0: # newQueue记录该马花费相同步数的可达的位置即BFS按层遍历的层 newQueue [] # 按层BFS for x, y, step in queue: for offsetX, offsetY in offsets: # 马走日到达的新位置 newX x offsetX newY y offsetY pos newX * n newY # 如果新位置越界或者已访问过则不能访问 if newX 0 or newX m or newY 0 or newY n or (pos in vis): continue # 将新位置加入新层 newQueue.append((newX, newY, step 1)) # 该马到达(newX, newY)位置最小步数为step1, 由于该马首次到达(newX, newY)位置因此step1就是最小步数 stepGrid[newX][newY] step 1 # 记录该马访问过该位置后续如果该马再次访问该位置则不是最小步数 vis.add(pos) queue newQueue k - 1 # 剩余步数减1 # BFS完后将公共可达位置reach和当前马可达位置vis取交集交集部分就是新的公共可达位置 reach vis # 算法入口 def getResult(): # 遍历棋盘 for i in range(m): for j in range(n): # 如果棋盘(i,j)位置是马 if grid[i][j] ! .: # 马的等级 k int(grid[i][j]) # 对该马进行BFS走日 bfs(i, j, k) # 如果所有马走完发现没有公共可达位置 if len(reach) 0: return -1 # 记录所有马都可达位置的最小步数和 minStep sys.maxsize for pos in reach: x pos // n y pos % n # (x,y)是所有马都可达的位置stepMap[x][y]记录所有马到达此位置的步数和 minStep min(minStep, stepGrid[x][y]) return minStep # 算法调用 print(getResult())C算法源码#include stdio.h #include limits.h #include math.h #define MAX_SIZE 26 // 棋盘行数, 棋盘列数 int m, n; // 棋盘矩阵 char map[MAX_SIZE][MAX_SIZE]; // 最小步数和矩阵stepMap[i][j]记录各个马走到棋盘(i,j)位置的最小步数之和 int stepMap[MAX_SIZE][MAX_SIZE] {0}; // 记录所有马都可达的公共位置坐标 int reach[MAX_SIZE * MAX_SIZE] {0}; int reach_size 0; // 马走日的偏移量 int offsets[8][2] {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}}; // 广搜 void bfs(int sx, int sy, int k) { // 广搜队列 int queue[m * n][3]; int queue_size 0; // (sx,sy)为马所在初始位置马到达初始位置需要0步 queue[queue_size][0] sx; queue[queue_size][1] sy; queue[queue_size][2] 0; queue_size; // 记录该马可以访问(sx,sy)位置 int vis[MAX_SIZE * MAX_SIZE] {0}; vis[sx * n sy] 1; // k记录该马剩余可走步数 while (queue_size 0 k 0) { // newQueue记录该马花费相同步数的可达的位置即BFS按层遍历的层 int newQueue[m * n][3]; int newQueue_size 0; // 按层BFS for (int i 0; i queue_size; i) { // 当前马所在位置(x,y)以及马到达该位置的步数step int x queue[i][0]; int y queue[i][1]; int step queue[i][2]; for (int j 0; j 8; j) { // 马走日到达的新位置 int newX x offsets[j][0]; int newY y offsets[j][1]; int pos newX * n newY; // 如果新位置越界或者已访问过则不能访问 if (newX 0 || newX m || newY 0 || newY n || vis[pos]) continue; // 将新位置加入新层 newQueue[newQueue_size][0] newX; newQueue[newQueue_size][1] newY; newQueue[newQueue_size][2] step 1; newQueue_size; // 该马到达(newX, newY)位置最小步数为step1, 由于该马首次到达(newX, newY)位置因此step1就是最小步数 stepMap[newX][newY] step 1; // 记录该马访问过该位置后续如果该马再次访问该位置则不是最小步数 vis[pos] 1; } } for (int i 0; i newQueue_size; i) { queue[i][0] newQueue[i][0]; queue[i][1] newQueue[i][1]; queue[i][2] newQueue[i][2]; } queue_size newQueue_size; k--; // 剩余步数减1 } // BFS完后将公共可达位置reach和当前马可达位置取交集交集部分就是新的公共可达位置 for (int i 0; i m * n; i) { if (reach[i] 1 vis[i] 0) { reach[i] 0; reach_size--; } } } int getResult() { // 遍历棋盘 for (int i 0; i m; i) { for (int j 0; j n; j) { // 如果棋盘(i,j)位置是马 if (map[i][j] ! .) { // 马的等级 int k map[i][j] - 0; // 对该马进行BFS走日 bfs(i, j, k); } } } // 如果所有马走完发现没有公共可达位置 if (reach_size 0) { return -1; } // 记录所有马都可达位置的最小步数和 int minStep INT_MAX; for (int i 0; i m * n; i) { if(reach[i] ! 1) continue; int x i / n; int y i % n; // (x,y)是所有马都可达的位置stepMap[x][y]记录所有马到达此位置的步数和 minStep (int) fmin(minStep, stepMap[x][y]); } return minStep; } int main() { scanf(%d %d, m, n); for (int i 0; i m; i) { scanf(%s, map[i]); for (int j 0; j n; j) { reach[i * n j] 1; } } reach_size m * n; printf(%d\n, getResult()); return 0; }