题目背景
西西艾弗岛某山脉深处出土了一台远古机器人,具体年代已不可考。初步修缮后,研究人员尝试操控机器人进行些简单的移动。
题目描述
整个实验场地被划分为 n×n 个方格,从 (1,1) 到 (n,n) 进行编号。机器人只能在这些方格间移动,不能走出场地范围。如下图所示,假设机器人当前位于 (x,y),那么接下来可以向周围八个方向跳跃移动(如果目标方格在场地范围内):

若机器人只能跳动不超过 k 步,场地内有多少方格(包括起始位置)可以抵达?
输入格式
从标准输入读入数据。 输入的第一行包含空格分隔的两个正整数 n 和 k,分别表示场地大小和跳动步数。 输入的第二行包含空格分隔的两个正整数 x 和 y,表示机器人的起始位置(保证位于场地内)。
输出格式
输出到标准输出。 输出一个整数,表示 k 步内可以抵达的方格总数。
样例 1 输入
4 1 1 1
样例 1 输出
3
样例 2 输入
4 2 1 1
样例 2 输出
8
样例 2 解释
如下图所示,初始位置、第一步和第二步跳跃抵达的位置总计为 8。

子任务
80% 的测试数据满足:k≤3; 全部的测试数据满足:n、k 均大于 0 且不超过 100。
题解
可以使用 BFS 或 DFS 进行搜索。在 DFS 实现中,步数作为递归函数的参数传递;而在 BFS 实现中,步数需要作为队列元素的附加参数存储。
实现细节
dx 和 dy 数组分别表示移动方向,st 数组用于记录访问状态,全局变量 cnt 统计已访问节点的数量。需要特别处理边界判断,同时统计的节点数包括所有经过的位置,而不仅仅是终点。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, k, x, y;
int a[N][N];
bool st[N][N];
int dx[8] = {, , , , , , , };
dy[] = {, , , , , , , };
cnt;
{
st[x][y] = ;
cnt++;
(num == k) ;
( i = ; i < ; i++) {
nx = x + dx[i];
ny = y + dy[i];
(nx < || nx > n || ny < || ny > n) ;
(!st[nx][ny]) {
(nx, ny, num + );
}
}
}
{
cin >> n >> k >> x >> y;
(x, y, );
cout << cnt;
}

