#P3262. 跳马(200分)
-
1000ms
Tried: 84
Accepted: 26
Difficulty: 6
所属公司 :
华为od
跳马(200分)
思路:BFS
首先我们考虑,如果只有一个马,那肯定是不需要移动的,因此对应的最小步数为0,如果是两个马,我们可以对这两个马分别跑一遍BFS,求这两个马到棋盘上每个点的最小距离(有的点受限于k可能到不了),如果有u个马,我们可以预处理出这m个马到棋盘上的所有距离(不能到达的点距离标记为无穷大),然后我们可以枚举整个棋盘的所有位置,枚举到(i,j)位置时,我们可以累加所有马到(i,j)点的最短距离,即为∑v=1udist[v][i][j],然后更新全局最小值,如果最终的最小值仍然为无穷大,则为无解,输出-1即可。
JavaScript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let n, m, dx, dy, dist, g = [], pos = [];
// 广度优先搜索函数,用于计算从马的当前位置出发到达(i, j)的最短距离
function bfs(x, y, u, k) {
const queue = [];
queue.push([x, y]);
dist[u][x][y] = 0;
while (queue.length > 0) {
const [x1, y1] = queue.shift();
// 遍历八个方向
for (let i = 0; i < 8; i++) {
const x2 = x1 + dx[i];
const y2 = y1 + dy[i];
// 检查新位置是否在棋盘内,是否满足条件
if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m &&
dist[u][x2][y2] > dist[u][x1][y1] + 1 &&
dist[u][x1][y1] < k) {
// 更新最短距离,并将新位置加入队列
dist[u][x2][y2] = dist[u][x1][y1] + 1;
queue.push([x2, y2]);
}
}
}
}
rl.on('line', (line) => {
const lines = line.trim().split(' ');
if (!n) {
// 读取第一行输入,初始化变量
n = parseInt(lines[0]);
m = parseInt(lines[1]);
dx = [1, 1, -1, -1, 2, 2, -2, -2];
dy = [-2, 2, -2, 2, -1, 1, -1, 1];
dist = {};
} else {
// 读取棋盘每一行的输入
const row = line.split('');
const i = g.length;
g.push(row);
for (let j = 0; j < m; j++) {
const u = i * m + j;
// 初始化每个马到所有位置的最短距离
dist[u] = Array.from({ length: n }, () => Array(m).fill(0x3f3f3f3f));
if ('1' <= row[j] && row[j] <= '9') {
// 如果当前位置有马,则进行广度优先搜索
bfs(i, j, u, parseInt(row[j]));
pos.push([i, j]); // 记录马的位置
}
}
}
}).on('close', () => {
// 计算所有可能的马的位置到每个空白格的最短距离和
let ans = 0x3f3f3f3f;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
let cnt = 0;
for (const p of pos) {
const u = p[0] * m + p[1];
if (dist[u][i][j] === 0x3f3f3f3f) {
cnt = 0x3f3f3f3f;
break;
}
cnt += dist[u][i][j];
}
ans = Math.min(ans, cnt);
}
}
// 输出结果
if (ans === 0x3f3f3f3f) {
console.log("-1");
} else {
console.log(ans);
}
});
Java
import java.util.*;
public class Main {
static final int N = 30;
static char[][] g = new char[N][N];
static int n, m;
static int[] dx = {1, 1, -1, -1, 2, 2, -2, -2};
static int[] dy = {-2, 2, -2, 2, -1, 1, -1, 1};
static HashMap<Integer, ArrayList<ArrayList<Integer>>> dist = new HashMap<>();
// BFS算法,计算从马的当前位置出发到达目标位置(i, j)的最短距离
static void bfs(int x, int y, int u, int k) {
Queue<AbstractMap.SimpleEntry<Integer, Integer>> q = new LinkedList<>();
q.add(new AbstractMap.SimpleEntry<>(x, y));
dist.get(u).get(x).set(y, 0);
while (!q.isEmpty()) {
AbstractMap.SimpleEntry<Integer, Integer> p = q.poll();
int x1 = p.getKey(), y1 = p.getValue();
for (int i = 0; i < 8; i++) {
int x2 = x1 + dx[i], y2 = y1 + dy[i];
// 判断是否越界,以及是否已经访问过,距离是否超过了k
if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m || dist.get(u).get(x2).get(y2) <= dist.get(u).get(x1).get(y1) + 1 || dist.get(u).get(x1).get(y1) >= k) {
continue;
}
dist.get(u).get(x2).set(y2, dist.get(u).get(x1).get(y1) + 1);
q.add(new AbstractMap.SimpleEntry<>(x2, y2));
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
ArrayList<AbstractMap.SimpleEntry<Integer, Integer>> pos = new ArrayList<>();
char[][] g = new char[n][m];
// 遍历输入地图
for (int i = 0; i < n; i++) {
String line = sc.next();
for (int j = 0; j < m; j++) {
int u = i * m + j;
dist.put(u, new ArrayList<>());
for (int p = 0; p < n; p++) {
ArrayList<Integer> row = new ArrayList<>();
for (int q = 0; q < m; q++) {
row.add(0x3f3f3f3f);
}
dist.get(u).add(row);
}
g[i][j] = line.charAt(j);
// 如果当前位置是马的起点,则进行BFS计算最短距离,并将起点位置加入pos列表
if (g[i][j] >= '1' && g[i][j] <= '9') {
bfs(i, j, u, g[i][j] - '0');
pos.add(new AbstractMap.SimpleEntry<>(i, j));
}
}
}
int ans = 0x3f3f3f3f;
// 遍历所有可能的目标位置
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int cnt = 0;
// 遍历所有马的起点位置,计算到达目标位置的总距离
for (AbstractMap.SimpleEntry<Integer, Integer> p : pos) {
int u = p.getKey() * m + p.getValue();
// 如果有某个马无法到达目标位置,则将cnt设为无穷大
if (dist.get(u).get(i).get(j) == 0x3f3f3f3f) {
cnt = 0x3f3f3f3f;
break;
}
cnt += dist.get(u).get(i).get(j);
}
// 更新最终答案为所有目标位置中的最小值
ans = Math.min(ans, cnt);
}
}
// 输出最终答案,如果无法到达任何目标位置,则输出-1
if (ans == 0x3f3f3f3f) System.out.println("-1");
else System.out.print(ans + System.lineSeparator());
}
}
Python
from collections import deque
N = 30
g = [[''] * N for _ in range(N)]
n, m = 0, 0
dx = [1, 1, -1, -1, 2, 2, -2, -2]
dy = [-2, 2, -2, 2, -1, 1, -1, 1]
dist = {}
def bfs(x, y, u, k):
q = deque([(x, y)])
dist[u][x][y] = 0
while q:
x1, y1 = q.popleft()
for i in range(8):
x2, y2 = x1 + dx[i], y1 + dy[i]
if 0 <= x2 < n and 0 <= y2 < m and dist[u][x2][y2] > dist[u][x1][y1] + 1 and dist[u][x1][y1] < k:
dist[u][x2][y2] = dist[u][x1][y1] + 1
q.append((x2, y2))
def main():
global n, m
global g
global dist
n, m = map(int, input().split())
pos = []
# 读取地图信息
for i in range(n):
line = input()
for j in range(m):
u = i * m + j
dist[u] = [[0x3f3f3f3f] * m for _ in range(n)]
g[i][j] = line[j]
if '1' <= g[i][j] <= '9':
# 对每个马的起点进行BFS计算最短距离,并将起点位置加入pos列表
bfs(i, j, u, int(g[i][j]))
pos.append((i, j))
ans = 0x3f3f3f3f
for i in range(n):
for j in range(m):
cnt = 0
for p in pos:
u = p[0] * m + p[1]
# 如果有某个马无法到达目标位置,则将cnt设为无穷大
if dist[u][i][j] == 0x3f3f3f3f:
cnt = 0x3f3f3f3f
break
cnt += dist[u][i][j]
# 更新最终答案为所有目标位置中的最小值
ans = min(ans, cnt)
# 输出最终答案,如果无法到达任何目标位置,则输出-1
if ans == 0x3f3f3f3f:
print("-1")
else:
print(ans)
if __name__ == "__main__":
main()
C++
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
char g[N][N]; // 存储地图
int n, m; // 地图的行数和列数
int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2}; // 马的移动方向(x轴)
int dy[8] = {-2, 2, -2, 2, -1, 1, -1, 1}; // 马的移动方向(y轴)
unordered_map<int, vector<vector<int>>> dist; // 标记从每一个马的当前位置出发到达(i, j)的最短距离
// BFS算法,计算从马的当前位置出发到达目标位置(i, j)的最短距离
void bfs(int x, int y, int u, int k) {
queue<pair<int, int>> q;
q.push({x, y});
dist[u][x][y] = 0;
while (q.size()) {
auto [x1, y1] = q.front();
q.pop();
for (int i = 0; i < 8; i++) {
int x2 = x1 + dx[i], y2 = y1 + dy[i];
// 判断是否越界,以及是否已经访问过,距离是否超过了k
if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m || dist[u][x2][y2] <= dist[u][x1][y1] + 1 || dist[u][x1][y1] >= k) {
continue;
}
dist[u][x2][y2] = dist[u][x1][y1] + 1;
q.push({x2, y2});
}
}
}
int main() {
cin >> n >> m; // 输入地图的行数和列数
vector<pair<int, int>> pos; // 存储马的初始位置
// 遍历输入地图
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int u = i * m + j;
dist[u] = vector<vector<int>>(n, vector<int>(m, 0x3f3f3f3f)); // 初始化距离为无穷大
cin >> g[i][j];
// 如果当前位置是马的起点,则进行BFS计算最短距离,并将起点位置加入pos列表
if (g[i][j] >= '1' && g[i][j] <= '9') {
bfs(i, j, u, g[i][j] - '0');
pos.push_back({i, j});
}
}
}
int ans = 0x3f3f3f3f; // 初始化最终答案为无穷大
// 遍历所有可能的目标位置
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int cnt = 0;
// 遍历所有马的起点位置,计算到达目标位置的总距离
for (auto &p : pos) {
int u = p.first * m + p.second;
// 如果有某个马无法到达目标位置,则将cnt设为无穷大
if (dist[u][i][j] == 0x3f3f3f3f) {
cnt = 0x3f3f3f3f;
break;
}
cnt += dist[u][i][j];
}
// 更新最终答案为所有目标位置中的最小值
ans = min(ans, cnt);
}
}
// 输出最终答案,如果无法到达任何目标位置,则输出-1
if (ans == 0x3f3f3f3f) puts("-1");
else cout << ans << endl;
return 0;
}
题目描述
马是象棋(包括中国象棋和国际象棋)中的棋子,走法是每步直一格再斜一格,即先横着或直着走一格,然后再斜着走一个对角线,可进可退,可越过河界,俗称马走“日”字。
给定 m 行 n 列的棋盘(网格图),棋盘上只有有棋子象棋中的棋子“马”,组每个棋子有等级之分,等级为 k 的可以跳 1 ~ k 步(走的方式与象棋中“马”的规则一样,不可以超出棋盘位置),问是否能将所有马跳到同一位置,如果存在,输出最少需要的总步数(每匹马的步数相加),不存在则输出 −1 。
注:
允许不同的马在跳的过程中跳到同一位置,坐标为 (x,y) 的马跳一次可以跳到到坐标为 $(x+1, y+2), (x+1, y-2), (x+2, y+1), (x+2, y-1), (x-1, y+2),(x-1, y-2), (x-2, y+1), (x-2, y-1)$的格点上,但是不可以超出棋盘范围。
输入描述
第一行输入 m , n 代表 m 行 n 列的网格图棋盘;
接下来输入 m 行 n 列的网格图棋盘,如果第 i 行,第 j 列的元素为“.”代表此格点没有棋子,如果为数字 k ,代表此格点存在等级为 k 的“马”。
- 1≤m,n≤25
- 1≤k≤9
输出描述
输出最少需要的总步数(每匹马的步数相加),不存在则输出 −1 。
示例1
输入
3 2
..
2.
..
输出
0
说明:
只有一匹马,不需要跳。
示例2
输入
3 5
47.48
4744.
7....
输出
17