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;
}
相关精彩链接
爱编程 玩科技 懂教育
领取专属 10元无门槛券
私享最新 技术干货