中南大学研究生机试题记录

有一个不聪明的机器人移入了一个w×h大小的迷宫，在其中既有可通行区域也有设置好的陷阱。他希望遍历整个迷宫的所有方格，但由于其缺乏智能性，在执行指令时存在局限性：每当面临无法继续移动的情况（即下一步移动将导致掉入陷阱或碰到迷宫边缘），它会向顺时针旋转90度（也就是向右转90度）。那么这个机器人最多能经过多少个方格呢？

输入

对于每组数据，第一行两个数w和h，表示迷宫的行和列(1<=w,h<=10)

在接下来的w行中，每行包含h个字符来描述这个迷宫的状态。其中，在该迷宫中存在一个英文字母（仅限于'U'、'D'、'L'、'R'四种），这些字母分别指示机器人起始时所面对的方向：上、下、左或右。具体而言，在该迷宫中：

• 'U'代表机器人初始指令为向上
• 'D'代表机器人初始指令为向下
• 'L'代表机器人初始指令为向左
• 'R'代表机器人初始指令为向右
  其余未被占据的位置则为空余区域

输出

对于每组数据，输出一个整数，即机器人一共经过多少个方格。

源代码：

#include <stdio.h>
#include <string.h>
const int maxnum = 10;
char maps[maxnum][maxnum];
int sx, sy;//起始坐标位置
int w, h;//输入的地图宽度与高度
const char dir[] = {"U", "R", "D", "L"};//方向序列采用顺时针排列
int visited[maxnum][maxnum];
int ans;//记录机器人能够移动的最大步数
int dx[] = {-1, 0, 1, 0}; //方向向量依次对应上、右、下、左四个方向
int dy[] = {0, 1, 0, -1};

void dfs(int x,int y,int dir,int steps){
//firstly:设当前所在点为已访问
visited[x][y]=1;
//secondly:找出机器人下一步的坐标
int newx=x+dx[dir]; //我觉得这里的一个路径表示很好，因为机器人只有四个方向可以走，所以坐标变动也很小，可以记住这种坐标表达方法
int newy=y+dy[dir];
//thirdly:判断下一步的坐标是否可以到达 (不能为陷阱，不能为边界，且还没有被访问过
if(newx>=0 && newx<w && newy>=0 && newy<h
&& maps[newx][newy]!=''
&& visited[newx][newy]==0 ){
dfs(newx,newy,dir,steps+1);
}else{
//下一步无法到达，则还可以顺时针转九十度
dir=(dir+1)%4;
int newx=x+dx[dir];
int newy=y+dy[dir];
if(newx>=0 && newx<w && newy>=0 && newy<h
&& maps[newx][newy]!=''
&& visited[newx][newy]==0 ){
dfs(newx,newy,dir,steps+1);
}else{
ans=steps;
return;
}
}
}
int main(){
while(scanf("%d%d",&w,&h)==2){
int cur=0;
for(int i=0;i<w;i++){
scanf("s",maps[i]);
for(int j=0;j<h;j++){
for (int k=0;k<4;k++){
if(maps[i][j]==dir[k]){
sx=i;
sy=j;
cur=k;
}
}
}
}
memset(visited,0,sizeof(visited));
ans=0;
dfs(sx,sy,cur,1);//递归调用dfs函数，该函数第一次调用表示的是在（sx，sy）为起点，方向为cur开始走迷宫，当前步数为1
printf("%d\n",ans);
}
return 0;
}