就是按照第一感觉来写的,直观的才是最好的
读完题后应该有下面的模拟思路
- 读入迷宫,找到起始点
- 从起始点出发,走到非法点
- 如果走到的点合法,cnt++(答案)并且重置转向机会并标记该点已经遍历
- 在非法点判断是否还有转向机会
- 有机会就转向
- 没机会就结束
然后我们一点一点来看其中的细节如何实现
1.什么情况下非法呢?
- 走出迷宫(数组越界情况)
- 遇到障碍(遇到’*’的情况)
- 走回头路(用st数组标记)
2.如何实现转向?
遍历四个方向需要dx,dy数组
我们观察不难发现,y总的dx,dy数组的方向是按照上右下左排列的
所以只需要循环向后遍历一位即可实现顺时针转动90°
最后只需用一个map存储URDL与对应方向的下标即可
比如对于起点为‘U’,{‘U’,0} 其方向为 dir = map[‘U’]
下一步的位置在 x + dx[dir],y + dy[dir]
3.初值问题
- 用于输出答案的cnt初值应该为1,因为就是在起点卡住,按照题意也是经历了一个格子
- 用于标记转向机会的flag初值为true,以为一开始就有转向机会,并在非法情况下被消耗,合法情况下被补充
- 对于起点为[x,y],标记数组中st[x][y]初值为true,表示已经来过此点
4.何时跳出循环?
当下一步非法并且失去转向机会时break
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 12;
char g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//U R D L
unordered_map<char,int> mp = {{'U',0},{'R',1},{'D',2},{'L',3},};
int main()
{
int n,m;
while(cin>>n>>m) //n行m列
{
memset(st, 0, sizeof st);
int x,y,dir;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
{
cin >> g[i][j];
if(g[i][j] != '.' && g[i][j] != '*')
{
x = i;
y = j;
dir = mp[g[i][j]];
}
}
int cnt = 1;
bool flag = true;
st[x][y] = true;
while(x < n && x >= 0 && y < m && y >= 0)
{
int nx =x + dx[dir],ny = y + dy[dir];
if(!(nx >=0 && nx<n && ny >=0 && ny<m) || g[nx][ny]=='*' || st[nx][ny])
{
//三种情况需要掉头:1.走出迷宫2.遇到障碍3.走到回头路
if(flag)
{
dir = (dir + 1) % 4;
flag = false;
}
else break;
}
else
{
x = nx;
y = ny ;
cnt ++;
st[x][y] = true;
flag = true;
}
}
printf("%d\n",cnt);
}
return 0;
}