[CSP-J 2024] 地图探险

题目描述

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

丛林的地图可以用一个 n 行 m 列的字符表来表示。我们将第 ii 行第 jj 列的位置的坐标记作 (i,j)(1≤i≤n,1≤j≤m)。如果这个位置的字符为 x，即代表这个位置上有障碍，不可通过。反之，若这个位置的字符为  .  ，即代表这个位置是一片空地，可以通过。

这个机器人的状态由位置和朝向两部分组成。其中位置由坐标 (x,y)(1≤x≤n,1≤y≤m) 刻画，它表示机器人处在地图上第 x 行第 y 列的位置。而朝向用一个 0∼3 的 整数 d 表示，其中 d=0 代表向东，d=1 代表向南，d=2 代表向西，d=3 代表向北。

初始时，机器人的位置为 (x0,y0)，朝向为 d0​。保证初始时机器人所在的位置为空地。接下来机器人将要进行 k 次操作。每一步，机器人将按照如下的模式操作：

小 A 想要知道，在机器人执行完 k 步操作之后，地图上所有被机器人经过的位置（包括起始位置）有几个。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 T，表示数据组数。

接下来包含 T 组数据，每组数据的格式如下：

第一行包含三个正整数 n,m,k。其中 n,m 表示地图的行数和列数，k 表示机器人执行操作的次数。

第二行包含两个正整数 x0,y0​ 和一个非负整数 d0。

接下来 n 行，每行包含一个长度为 m 的字符串。保证字符串中只包含 xx 和 .. 两个字符。其中，第 x 行的字符串的第 y 个字符代表的位置为 (x,y)。这个位置是 x 即代表它是障碍，否则代表它是空地。数据保证机器人初始时所在的位置为空地。

输出格式

输入输出样例

输入 #1

2 1 5 4 1 1 2 ….x 5 5 20 1 1 0 ….. .xxx. .x.x. ..xx. x….

输出 #1

3 13

数据范围与提示

对于所有测试数据，保证：1≤T≤5,1≤n,m≤103，1≤k≤1061≤k≤106，1≤x0≤n，1≤y0≤m，0≤d0≤3，且机器人的起始位置为空地。

分析

         说难听点，这题纯**

一开始，我分析了很久，结果随手写了个纯暴力代码结果就过了！

（这里，我提醒所有基友们，遇到难题，千万不要想太太太太太久，实在没思路，就写一个暴力，说不定还能全对，或者也能捞点分，还会为后面的思考奠定基础。）

代码

#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char mp[1010][1010];
bool vis[1010][1010];
int main(){
int T;
cin>>T;
while(T–){
memset(vis,0,sizeof vis);
memset(mp,0,sizeof mp);
int n,m,k,x,y,d,sum;
cin>>n>>m>>k>>x>>y>>d;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cin>>mp[i][j];
}
sum=1,vis[x][y]=1;
while(k–){
int nx=x+dx[d],ny=y+dy[d];
if(mp[nx][ny]=='.'){
if(vis[nx][ny]==0)sum++,vis[nx][ny]=1;
x=nx,y=ny;
}else d=(d+1)%4;
}
cout<<sum<<endl;
}
return 0;
}

AC！