T2[CSP-J 2024] 地图探险

T2[CSP-J 2024] 地图探险

题目描述

小 A 打算前往一片丛林去探险。丛林的地理环境十分复杂，为了防止迷路，他先派遣了一个机器人前去探路。

丛林的地图可以用一个

行

列的字符表来表示。我们将第

行第

列的位置的坐标记作（

，

）（

，

）。如果这个位置的字符为

，即代表这个位置上有障碍，不可通过。反之，若这个位置的字符为

，即代表这个位置是一片空地，可以通过。

这个机器人的状态由位置和朝向两部分组成。其中位置由坐标（

，

）（

，

）刻画，它表示机器人处在地图上第

行第

列的位置。而朝向用一个

的 整数

表示，其中

代表向东，

代表向南，

代表向西，

代表向北。

初始时，机器人的位置为（

，

），朝向为

。初始时，机器人的位置为。接下来机器人将要进行

次操作。每一步，机器人将按照如下的模式操作：

假设机器人当前处在的位置为（

，

），朝向为

。则它的方向上的下一步的位置（

，

）定义如下：若

，则令（

，

）

（

，

），若

，则令（

，

）

（

，

），若

，则令（

，

）

（

，

），若

，则令（

，

）

（

，

）。

接下来，机器人判断它下一步的位置是否在地图内，且是否为空地。具体地说，它判断（

，

）是否满足

，

，且（

，

）位置上是空地。如果条件成立，则机器人会向前走一步。它新的位置变为（

，

），且朝向不变。如果条件不成立，则它会执行“向右转”操作。也就是说，令

（

）

（即

除以

的余数），且它所处的位置保持不变，但朝向由

变为

。

小 A 想要知道，在机器人执行完

步操作之后，地图上所有被机器人经过的位置（包括起始位置）有几个。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数

，表示数据组数。

接下来包含

组数据，每组数据的格式如下：

第一行包含三个正整数

，

，

。其中

，

表示地图的行数和列数，

表示机器人执行操作的次数。

第二行包含两个正整数

，

和一个非负整数

。

接下来

行，每行包含一个长度为

的字符串。保证字符串中只包含

和

两个字符。其中，第

行的字符串的第

个字符代表的位置为（

，

）。这个位置是

即代表它是障碍，否则代表它是空地。数据保证机器人初始时所在的位置为空地。

输出格式

对于每组数据：输出一行包含一个正整数，表示地图上所有被机器人经过的位置（包括起始位置）的个数。

样例输入 #1

2

1 5 4

1 1 2

....x

5 5 20

1 1 0

.....

.xxx.

.x.x.

..xx.

x....

样例输出 #1

3

13

提示

【样例 1 解释】

该样例包含两组数据。对第一组数据，机器人的状态以如下方式变化：

初始时，机器人位于位置

，方向朝西（用数字

代表）。

第一步，机器人发现它下一步的位置

不在地图内，因此，它会执行“向右转”操作。此时，它的位置仍然为

，但方向朝北（用数字

代表）。

第二步，机器人发现它下一步的位置

不在地图内，因此，它仍然会执行“向右转”操作。此时，它的位置仍然为

，但方向朝东（用数字

代表）。

第三步，机器人发现它下一步的位置

在地图内，且为空地。因此，它会向东走一步。此时，它的位置变为

，方向仍然朝东。

第四步，机器人发现它下一步的位置

在地图内，且为空地。因此，它会向东走一步。此时，它的位置变为

，方向仍然朝东。

因此，四步之后，机器人经过的位置有三个，分别为

。

对第二组数据，机器人依次执行的操作指令为：向东走到

，向东走到

，向东走到

，向东走到

，向右转，向南走到

，向南走到

，向南走到

，向南走到

，向右转，向西走到

，向西走到

，向西走到

，向右转，向北走到

，向右转，向右转，向南走到

，向右转，向右转。

【数据范围】

对于所有测试数据，保证：

，

，

，

，

，

，

，且机器人的起始位置为空地。

标程1

#include<bits/stdc++.h>

using namespace std;

int vis[1005][1005];

char a[1005][1005];

int t,n,m,k;

int x,y,d;

string s;

int main(){

cin >> t;

while(t--){

cin >> n >> m >> k;

cin >> x >> y >> d;

//初始化地图

memset(vis,0,sizeof(vis));

// 输入地图

for(int i = 1; i <= n; i++){

for(int j = 1; j <= m; j++)cin >> a[i][j];

}

vis[x][y] = 1; // 初始开始位置

// 模拟过程

for(int i = 1; i <= k; i++){

int nx,ny;

//下一步的位置

if(d == 0){

nx = x,ny = y+1;

}

else if(d == 1){

nx = x +1,ny = y;

}

else if(d == 2){

nx = x,ny = y-1;

}

else if(d == 3){

nx = x -1,ny = y;

}

// 断它下一步的位置是否在地图内，且是否为空地

if(nx >= 1&&nx <= n&&ny>=1&&ny<=m&&a[nx][ny] == '.'){

x = nx;

y = ny;

vis[nx][ny] = 1;

}else{

d = (d+1) %4;

}

}

// 统计位置数量

int ans = 0;

for(int i = 1; i <= n; i++){

for(int j = 1; j <= m; j++){

if(vis[i][j])ans++;

}

}

//输出答案

cout << ans << "\n";

}

return 0;

}

相关精彩链接

爱编程  玩科技  懂教育