机器人复健指南

时间限制： 1.0 秒

空间限制： 512 MiB

相关文件： 题目目录

题目背景

西西艾弗岛某山脉深处出土了一台远古机器人，具体年代已不可考。初步修缮后，研究人员尝试操控机器人进行些简单的移动。

题目描述

整个实验场地被划分为 个方格，从 到 进行编号。机器人只能在这些方格间移动，不能走出场地范围。
如下图所示，假设机器人当前位于 ，那么接下来可以向周围八个方向跳跃移动（如果目标方格在场地范围内）：

p02-01.png

若机器人只能跳动不超过 步，场地内有多少方格（包括起始位置）可以抵达？

输入格式

从标准输入读入数据。

输入的第一行包含空格分隔的两个正整数 和 ，分别表示场地大小和跳动步数。

输入的第二行包含空格分隔的两个正整数 和 ，表示机器人的起始位置（保证位于场地内）。

输出格式

输出到标准输出。

输出一个整数，表示 步内可以抵达的方格总数。

样例1输入

4 1
1 1

样例1输出

3

样例2输入

4 2
1 1

样例2输出

8

样例2解释

如下图所示，初始位置、第一步和第二步跳跃抵达的位置总计为 。

p02-02.png

子任务

的测试数据满足：；

全部的测试数据满足：、 均大于 且不超过 。

解题思路

每次跳跃都可以按照图示到达 8 个方向，坐标变化为 或 （即国际象棋中的马步）。因此把每个方格看成图中的一个结点、一次跳跃看成一条边。题目要求统计从起点出发 至多 跳跃 步能到达的不同方格数，使用广度优先搜索（BFS）即可。

定义 dist[i][j] 为起点到方格 (i, j) 的最少跳跃次数，初始全部为 -1。将起点入队并令其距离为 0；每次取出一个方格后，枚举 8 个方向：

1. 若目标格子在场地内且尚未访问，则令其距离为当前距离加 1；
2. 只有新距离不超过 k 时才入队，并将答案加一；
3. BFS 结束时，答案即为所有距离不超过 k 的方格数（起点已在初始时计入）。

每个方格最多入队一次，每次枚举 8 个方向，因此时间复杂度为 ，空间复杂度为 。

Java 参考代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
    static class FastScanner {
        private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer;

        int nextInt() throws IOException {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return Integer.parseInt(tokenizer.nextToken());
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner scanner = new FastScanner();
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int startX = scanner.nextInt() - 1;
        int startY = scanner.nextInt() - 1;

        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = -1;
            }
        }

        int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
        int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{startX, startY});
        dist[startX][startY] = 0;
        int answer = 1;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];

            //到底k步，不跳了
            if (dist[x][y] == k) {
                continue;
            }

            for (int direction = 0; direction < 8; direction++) {
                int nextX = x + dx[direction];
                int nextY = y + dy[direction];

                if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n
                        || dist[nextX][nextY] != -1) {
                    //越界或者是访问过的节点，跳过
                    continue;
                }

                dist[nextX][nextY] = dist[x][y] + 1;
                queue.offer(new int[]{nextX, nextY});
                answer++;
            }
        }

        System.out.println(answer);
    }
}