有一个愚蠢的机器人走进一个 w×h的迷宫，迷宫里有空地和陷阱。
他想要访问迷宫的每个方格，但是它很笨，只会按照指令的方向走。
当机器人不能走的时候，也就是下一步会遇到陷阱、迷宫边界或者访问过的格子时，它会向右转 90度(顺时针旋转 90度，不能访问已经访问过的方格，且在原地只转一次，移动后可获得又一次旋转机会)。
请问这个机器人最多可以经过多少个方格。
输入格式
输入包含多组测试数据。
每组数据第一行包含两个整数 w,h。
接下来 w行每行有 h 个字符用于描述这个迷宫。其中 . 表示空地，即为可以走的地方。* 表示陷阱，即为不能走的地方。其中还有且仅有一个英文字母，表示机器人的出发点，字母只有 U，D，L，R 四种。分别表示机器人的初始指令是向上，向下，向左，向右。
输出格式
每组数据，输出一行，一个整数，即机器人一共经过多少个方格。
数据范围
1≤w,h≤10
输入样例：
2 3
U..
.*.
4 4
R...
.**.
.**.
....
输出样例：
4
12
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int w,h;
const int N = 15;
char g[N][N];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
bool st[N][N];
typedef pair<int,int> PII;
int bfs(char gg,int idx,int idy)
{
queue<PII> q;
memset(st,0,sizeof st);
int res = 0;
q.push({idx,idy});
while(q.size())
{
int a = q.front().first;
int b = q.front().second;
q.pop();
if(gg == 'U')
{
int x = a - 1;
int y = b;
if(!st[x][y] && g[x][y] == '.' && x>=0 && x<w && y>=0 && y<h)
{
res++;
q.push({x,y});
st[x][y] = true;
}
else
{
x = a;
y = b + 1;
if(!st[x][y] && g[x][y] == '.'&& x>=0 && x<w && y>=0 && y<h)
{
res++;
q.push({x,y});
gg = 'R';
st[x][y] = true;
}
}
}
else if(gg == 'D')
{
int x = a + 1;
int y = b;
if(!st[x][y] && g[x][y] == '.'&& x>=0 && x<w && y>=0 && y<h)
{
res++;
q.push({x,y});
st[x][y] = true;
}
else
{
x = a;
y = b - 1;
if(!st[x][y] && g[x][y] == '.'&& x>=0 && x<w && y>=0 && y<h)
{
res++;
q.push({x,y});
gg = 'L';
st[x][y] = true;
}
}
}
else if(gg == 'L')
{
int x = a;
int y = b - 1;
if(!st[x][y] && g[x][y] == '.'&& x>=0 && x<w && y>=0 && y<h)
{
res++;
q.push({x,y});
st[x][y] = true;
}
else
{
x = a - 1;
y = b;
if(!st[x][y] && g[x][y] == '.'&& x>=0 && x<w && y>=0 && y<h)
{
res++;
q.push({x,y});
gg = 'U';
st[x][y] = true;
}
}
}
else
{
int x = a;
int y = b + 1;
if(!st[x][y] && g[x][y] == '.'&& x>=0 && x<w && y>=0 && y<h)
{
res++;
q.push({x,y});
st[x][y] = true;
}
else
{
x = a + 1;
y = b;
if(!st[x][y] && g[x][y] == '.'&& x>=0 && x<w && y>=0 && y<h)
{
res++;
q.push({x,y});
gg = 'D';
st[x][y] = true;
}
}
}
}
return res;
}
int main()
{
while(cin>>w>>h)
{
int idx = -1,idy = -1;
for(int i=0;i<w;i++)
{
for(int j=0;j<h;j++)
{
cin>>g[i][j];
if(g[i][j] != '.' && g[i][j] != '*')
{
idx = i;
idy = j;
}
}
}
cout<<bfs(g[idx][idy],idx,idy)+1<<endl;
}
return 0;
}
来源：中南大学考研机试题 -来自Acwing收录:
https://www.acwing.com/