P1747 好奇怪的游戏

calendar May 9, 2026 · 7 分钟阅读 · 广度优先搜索 最短路径  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1747
难度 普及
知识点 BFS、最短路径、队列

题目描述

有一个 19 × 19 的棋盘，左上角为 (1, 1)。棋子"好奇怪"的移动方式与象棋中的马类似，有 12 种可能的走法。给定好奇怪的起始位置，求它走到 (1, 1) 的最少步数。

本题有 两次查询，每次独立计算并输出答案。

解题思路

核心思想

将棋盘建模为图，每个格子是一个结点，合法的移动是边。使用 BFS（广度优先搜索） 按层扩展，第一次到达 (1, 1) 时的步数即为最短路径长度。

算法步骤

  1. 用 g[20][20] 标记每个位置是否已访问（true 表示未访问，false 表示已访问/障碍）
  2. 将起始位置入队，步数为 0
  3. BFS 逐层扩展：出队一个位置，尝试所有 12 种走法
  4. 若走到 (1, 1)，当前步数 +1 即为答案
  5. 标记已访问，将新位置入队（步数 +1）

因为输入有 两次查询，每次 BFS 前需要重置 g 数组和队列。

完整代码

C++

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct point {
    int x, y, s;  // s 为当前步数
};

bool g[20][20];
queue<point> q;

// 12 种"马"的走法偏移量
int xx[12] = {1, 2, 2, 1, -1, -2, -2, -1, 2, 2, -2, -2};
int yy[12] = {-2, -1, 1, 2, 2, 1, -1, -2, -2, 2, 2, -2};

// 检查位置是否合法（在棋盘内且未访问）
bool check(int x, int y) {
    if (x < 1 || y < 1 || x > 19 || y > 19) return false;
    if (!g[x][y]) return false;  // 已访问或为障碍
    return true;
}

void bfs(int x, int y) {
    q.push({x, y, 0});  // 起始位置，步数为 0
    g[x][y] = false;       // 标记起点已访问

    while (!q.empty()) {
        point f = q.front();
        q.pop();

        for (int i = 0; i < 12; ++i) {
            int nx = f.x + xx[i];
            int ny = f.y + yy[i];

            if (check(nx, ny)) {
                if (nx == 1 && ny == 1) {
                    // 找到目标，输出答案（当前步数 + 1）
                    cout << f.s + 1 << endl;
                    return;  // 结束整个程序
                }
                g[nx][ny] = false;
                q.push({nx, ny, f.s + 1});
            }
        }
    }
}

int main() {
    int tx = 0, ty = 0;

    // 第一次查询
    memset(g, true, sizeof(g));  // 重置棋盘
    while (!q.empty()) q.pop();     // 清空队列
    cin >> tx >> ty;
    bfs(tx, ty);

    // 第二次查询
    memset(g, true, sizeof(g));  // 重置棋盘
    while (!q.empty()) q.pop();     // 清空队列
    cin >> tx >> ty;
    bfs(tx, ty);

    return 0;
}

关键代码讲解

1. 棋子走法定义

int xx[12] = {1, 2, 2, 1, -1, -2, -2, -1, 2, 2, -2, -2};
int yy[12] = {-2, -1, 1, 2, 2, 1, -1, -2, -2, 2, 2, -2};

这 12 种偏移对应象棋中"马走日"的 8 个方向 + 重复走法（题目特意包含重复，不影响正确性）。

2. BFS 核心循环

while (!q.empty()) {
    point f = q.front();
    q.pop();
    for (int i = 0; i < 12; ++i) {
        int nx = f.x + xx[i];
        int ny = f.y + yy[i];
        if (check(nx, ny)) { ... }
    }
}

逐层扩展，队列中每个元素记录 (x, y, 步数)。出队后枚举 12 种走法，找到 (1,1) 立即输出答案。

3. 两次查询的重置

memset(g, true, sizeof(g));  // 重置所有位置为"未访问"
while (!q.empty()) q.pop();    // 清空上一次的队列

两次查询相互独立，必须重置状态。

复杂度分析

方法 时间复杂度 空间复杂度
BFS O(19 × 19) = O(361)（每个位置最多入队一次） O(19 × 19)（访问标记数组）

注意：g[20][20] 用 bool 只需 ~400 字节，空间非常宽裕。

易错点

  1. 结构体初始化：C++11 以后可以用 {x, y, s} 初始化 struct，但不能写 (point){x,y,s}（这是 C 语言的写法）。
  2. 重置状态：两次查询之间必须 memset(g, true, ...) + 清空队列，否则会沿用上一次的访问标记。
  3. check 函数的短路求值：if (x<1 || y<1 || x>19 || y>19) return false; 必须先写，防止数组越界。

其他语言解法

Python

from collections import deque

def bfs(sx: int, sy: int) -> int:
    """BFS 求 (sx,sy) 到 (1,1) 的最短步数"""
    g = [[True] * 20 for _ in range(20)]  # True 表示未访问
    q = deque()
    q.append((sx, sy, 0))
    g[sx][sy] = False

    # 12 种马走日偏移
    dx = [1, 2, 2, 1, -1, -2, -2, -1, 2, 2, -2, -2]
    dy = [-2, -1, 1, 2, 2, 1, -1, -2, -2, 2, 2, -2]

    while q:
        x, y, s = q.popleft()
        for i in range(12):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 1 or ny < 1 or nx > 19 or ny > 19:
                continue
            if not g[nx][ny]:
                continue
            if nx == 1 and ny == 1:
                return s + 1
            g[nx][ny] = False
            q.append((nx, ny, s + 1))
    return -1  # 理论上不会执行到这里

if __name__ == "__main__":
    tx, ty = map(int, input().split())
    print(bfs(tx, ty))
    tx, ty = map(int, input().split())
    print(bfs(tx, ty))

JavaScript

'use strict';

function bfs(sx, sy) {
    // g[x][y] = true 表示未访问
    const g = Array.from({ length: 20 }, () => Array(20).fill(true));
    const q = [{ x: sx, y: sy, s: 0 }];
    g[sx][sy] = false;

    const dx = [1, 2, 2, 1, -1, -2, -2, -1, 2, 2, -2, -2];
    const dy = [-2, -1, 1, 2, 2, 1, -1, -2, -2, 2, 2, -2];

    let head = 0;
    while (head < q.length) {
        const { x, y, s } = q[head++];
        for (let i = 0; i < 12; ++i) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx < 1 || ny < 1 || nx > 19 || ny > 19) continue;
            if (!g[nx][ny]) continue;
            if (nx === 1 && ny === 1) return s + 1;
            g[nx][ny] = false;
            q.push({ x: nx, y: ny, s: s + 1 });
        }
    }
    return -1;
}

const fs = require('fs');
const lines = fs.readFileSync(0, 'utf8').trim().split('\n');
const [tx1, ty1] = lines[0].split(' ').map(Number);
console.log(bfs(tx1, ty1));
const [tx2, ty2] = lines[1].split(' ').map(Number);
console.log(bfs(tx2, ty2));

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

var g [20][20]bool
var q [400][3]int // x, y, s
var head, tail int

func bfs(sx, sy int) int {
    // 重置 g 数组
    for i := 1; i <= 19; i++ {
        for j := 1; j <= 19; j++ {
            g[i][j] = true
        }
    }
    head, tail = 0, 0
    q[tail][0], q[tail][1], q[tail][2] = sx, sy, 0
    tail++
    g[sx][sy] = false

    dx := []int{1, 2, 2, 1, -1, -2, -2, -1, 2, 2, -2, -2}
    dy := []int{-2, -1, 1, 2, 2, 1, -1, -2, -2, 2, 2, -2}

    for head < tail {
        x, y, s := q[head][0], q[head][1], q[head][2]
        head++
        for i := 0; i < 12; i++ {
            nx, ny := x+dx[i], y+dy[i]
            if nx < 1 || ny < 1 || nx > 19 || ny > 19 {
                continue
            }
            if !g[nx][ny] {
                continue
            }
            if nx == 1 && ny == 1 {
                return s + 1
            }
            g[nx][ny] = false
            q[tail][0], q[tail][1], q[tail][2] = nx, ny, s+1
            tail++
        }
    }
    return -1
}

func main() {
    in := bufio.NewReader(os.Stdin)
    var tx, ty int
    fmt.Fscan(in, &tx, &ty)
    fmt.Println(bfs(tx, ty))
    fmt.Fscan(in, &tx, &ty)
    fmt.Println(bfs(tx, ty))
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] g = new boolean[20][20];
    static Queue<int[]> q = new LinkedList<>();

    static int[] dx = {1, 2, 2, 1, -1, -2, -2, -1, 2, 2, -2, -2};
    static int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2, -2, 2, 2, -2};

    static boolean check(int x, int y) {
        if (x < 1 || y < 1 || x > 19 || y > 19) return false;
        if (!g[x][y]) return false;
        return true;
    }

    static void bfs(int sx, int sy) throws Exception {
        q.clear();
        for (int i = 1; i <= 19; i++)
            Arrays.fill(g[i], true);

        q.offer(new int[]{sx, sy, 0});
        g[sx][sy] = false;

        while (!q.isEmpty()) {
            int[] f = q.poll();
            for (int i = 0; i < 12; i++) {
                int nx = f[0] + dx[i];
                int ny = f[1] + dy[i];
                if (check(nx, ny)) {
                    if (nx == 1 && ny == 1) {
                        System.out.println(f[2] + 1);
                        return;
                    }
                    g[nx][ny] = false;
                    q.offer(new int[]{nx, ny, f[2] + 1});
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        int tx = sc.nextInt(), ty = sc.nextInt();
        bfs(tx, ty);
        tx = sc.nextInt(); ty = sc.nextInt();
        bfs(tx, ty);
    }

    static class FastScanner {
        private final BufferedInputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) {
            in = new BufferedInputStream(is);
        }

        private int readByte() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c, sign = 1, val = 0;
            do { c = readByte(); } while (c <= ' ' && c != -1);
            if (c == '-') { sign = -1; c = readByte(); }
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = readByte();
            }
            return val * sign;
        }
    }
}