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

题目背景

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

题目描述

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

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

输入格式

从标准输入读入数据。

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

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

输出格式

输出到标准输出。

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

样例1输入

4 1
1 1

样例1输出

样例2输入

4 2
1 1

样例2输出

样例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;
}

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2501_92845263/article/details/151046113