信息学奥赛一本通 2112：【24CSPJ普及组】地图探险（explore） | 洛谷 P11228 [CSP-J 2024] 地图探险
【题目链接】
ybt 2112：【24CSPJ普及组】地图探险（explore）
洛谷 P11228 [CSP-J 2024] 地图探险
【题目考点】
1. 模拟
2. 二维数组
3. 方向数组
在一个矩阵中，当前位置为(sx, sy)，将下一个位置与当前位置横纵坐标的差值记到一个数组中，即为方向数组。
设方向数组dir[4][2]
dir[i][0]表示下一步到达位置的行号和当前位置行号的差值dir[i][1]表现下一步到达位置的列号和当前位置列号的差值。
以遍历上下左右四个方向为例：
- 二维数组写法
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
for(int i = 0; i < 4; ++i)
{
int x = sx + dir[i][0], y = sy + dir[i][1];
//(sx,sy)周围的一个新的位置为(x, y)
}
【解题思路】
题目中已经给出了表示方向的方法：整数d表示机器人前进的方向，d = 0 代表向东（右），d = 1 代表向南（下），d = 2 代表向西（左），d = 3 代表向北（上）。向右转操作为d = (d+1)%4。
设方向数组dir[4][2]，dir[d]表示向整数d代表的方向走一步后，新位置和原位置横纵坐标的差值。
dir[0]表示向右走一步新的位置和当前位置横纵坐标的差值，即dir[0][0]=0, dir[0][1] = 1，或写为dir[0] = {0, 1}
dir[1]表示向下走一步后新的位置和当前位置横纵坐标的差值，dir[1] = {1, 0}
dir[2]表示向左走一步后新的位置和当前位置横纵坐标的差值，dir[2] = {0, -1}
dir[3]表示向上走一步后新的位置和当前位置横纵坐标的差值，dir[3] = {-1, 0}
所以将方向数组声明为int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
设vis数组记录一个位置是否已访问过，设ans记录经过的位置数量。
从起始位置开始一共需要走k步
每走一步前，先通过当前位置和方向数组求出下一个位置的坐标
- 如果下一个位置在地图范围内，而且是空地，不是障碍，那么可以走到下一个位置
- 如果下一个位置没有访问过，那么将该位置标记为已访问过，经过的位置数量加1。
- 如果下一个位置已访问过，则不做事情。
- 如果下一个位置不是空地，那么进行右转操作。
该题是模拟类问题，题目描述已经足够细致，按照题目描述逐步实现即可。
注意该问题是多组数据问题，处理每组数据前需要清空相关变量，比如vis数组，和ans变量。
【题解代码】
解法1：模拟
#include<bits/stdc++.h>
using namespace std;
#define N 1005
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//方向：右下左上
char mp[N][N];
bool vis[N][N];//vis[i][j]：(i,j)位置是否已访问过
int main()
{
int t, n, m, k, sx, sy, d, ans;
cin >> t;
while(t--)
{
cin >> n >> m >> k >> sx >> sy >> d;//(sx, sy)当前位置
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
cin >> mp[i][j];
memset(vis, 0, sizeof(vis));
vis[sx][sy] = true;//经过起始位置
ans = 1;//ans：经过的位置的数量
for(int i = 1; i <= k; ++i)//走k步
{
int x = sx+dir[d][0], y = sy+dir[d][1];//(x,y)下一步要走到的位置
if(x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] == '.')//如果(x,y)在地图内，且是空地
{
if(!vis[x][y])
{
vis[x][y] = true;
ans++;
}
sx = x, sy = y;
}
else
d = (d+1)%4;//右转
}
cout << ans << endl;
}
return 0;
}