1010: 机器人走迷宫

实现代码：

#include <iostream>
#include <stdio.h>
#include <string.h> 
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

struct Status{
	int x,y;
	int t;
	int d; 
};

queue<Status> Q; 
bool mark[20][20] = {false};
char maze[20][20];

int getDr(char c){// 获得朝向 
	switch(c){
		case 'U':
			return 0;
		case 'R':
			return 1;
		case 'D':
			return 2;
		case 'L':
			return 3;		
	} 
} 

bool result(int x,int y){  // 判断当前位置是否是结果 
	if(mark[x-1][y]==true&&mark[x+1][y]==true&&mark[x][y-1]==true&&mark[x][y+1]==true){
		return true;
	}
	return false;
}

void getNextLocation(int *x,int* y,Status &s){
	if(s.d==0){
		*x = s.x-1;
		*y = s.y;
		return;
	}
	if(s.d==1){
		*x = s.x;
		*y = s.y+1;
		return;
	}
	if(s.d==2){
		*x = s.x+1;
		*y = s.y;
		return;
	}
	if(s.d==3){
		*x = s.x;
		*y = s.y-1;
		return;
	}
}

int BFS(int w,int h){
	while(!Q.empty()){
		Status cur = Q.front();
		Q.pop();
		if(result(cur.x,cur.y))return cur.t; // 在BFS中 要弄清楚目标状态是什么  如果是目标状态 返回结果
		 
		int nx;
		int ny;
		getNextLocation(&nx,&ny,cur);
		if(mark[nx][ny]==true||maze[nx][ny]=='*'){
			mark[nx][ny] = true;
			cur.d = (cur.d+1)%4; // 右转
			Q.push(cur);
			continue; 
		}else{
			mark[nx][ny] = true;
			cur.x = nx;
			cur.y = ny;
			cur.t = cur.t+1;
			Q.push(cur);
			continue;
		}
		
	}
	return 1;
}


int main(int argc, char** argv) {
	int w,h;
	while(scanf("%d%d",&w,&h)){
		// 清空上一次的数据 
		while (!Q.empty()) {
			Q.pop();
		}
		for (int i = 0; i < 20; i++) {
			for (int j = 0; j < 20; j++) {
				mark[i][j] = false;
				maze[i][j] = 0;
			}
		}
		
		// 进入这一次的输入 
		for(int i=1;i<=w;i++){
			scanf("%s",maze[i]+1);
		}
	
		mark[1][1] = true;
		for(int i=0;i<=w+1;i++){
			mark[i][0] = true;
			mark[i][h+1] = true;
		}
		for(int j=0;j<=h+1;j++){
			mark[0][j] = true;
			mark[w+1][j] = true;
		}
		
	
		Status temp;
		temp.x=temp.y=temp.t=1;
		temp.d = getDr(maze[1][1]);
		Q.push(temp);
		int ret = BFS(w,h);
		printf("%d\n",ret);
		//printf("%c",maze[1][1]); 
	}

	return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：1010: 机器人走迷宫，转载请注明来源！