CCF-CSP第38次认证第二题——机器人复健指南（满分题解）

题目背景

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

题目描述

整个实验场地被划分为 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]={1,2,1,2,-1,-2,-1,-2},dy[8]={2,1,-2,-1,2,1,-2,-1}; int cnt; void dfs(int x,int y,int num){ st[x][y]=true; cnt++; if(num==k)return; for(int i=0;i<8;i++){ int a=x+dx[i],b=y+dy[i]; if(a<1||a>n||b<1||b>n)continue; if(!st[a][b]){ dfs(a,b,num+1); } } } int main(){ cin>>n>>k>>x>>y; dfs(x,y,0); cout<<cnt; }