QDU 帅气的HYC迷路了（简单搜索+小小模拟）

帅气的HYC迷路了

发布时间: 2015年11月1日 17:02   最后更新: 2015年11月1日 18:40   时间限制: 1000ms   内存限制: 128M

描述

 有一天, 我们帅气的HYC找到了一张藏宝图, 这张图很神奇, 只要你看它一眼, 立马就会被传送到一个迷宫里, 这个迷宫仅有一个出口.那么现在问题来啦, 问你找到这个出口需要走多少步?

    现在给出HYC在迷宫房中走的规则, HYC每走出一步, 都会优先向左走, 如果左边是墙, 那么他会向前走, 如果前边也是墙, 那么他就会向右走, 如果右边也是墙, 那么他只能选择后退了~~~~>_<~~~~

    另外, HYC也想知道如果不这样走, 他最少能走多少步能走出出口呢?

输入

首先给出一个T (1 <= T < 100) 代表T组测试数据

每组测试数据第一行为两个整数r 和 c (3 <= r,c <= 40) r代表这个迷宫有多少列,c代表这个迷宫有多少行.

S表示入口, E表示出口, #表示墙不能走, .表示空白区域, 可以走.

题目保证给出的迷宫四周都是墙, 而且按照规则走总能找到出口, 且初始方向为向北走,快来帮帮他吧!

输出

每组数据输出两个数, 第一个数表示按照规则走的步数, 第二个数表示走到出口最短需要多少步.

样例输入1  复制

1
9 5
#########
#.#.#.#.#
S.......E
#.#.#.#.#
#########      

样例输出1

17 9      

好久没写过搜索，都手生了，WA了好几发啊。

按照规则走就是dfs，最短走就是bfs，bfs好写，dfs需要考虑方向的转换，以及后退时也算走一步的处理。

#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
using namespace std;
struct node{
	int x, y, stp;
} ft, tl;
queue<node> q;
int nt[4][2] = {0, -1, -1, 0, 0, 1, 1, 0};
int dnt[4][4][2] = {0, -1, -1, 0, 0, 1, 1, 0, -1, 0, 0, 1, 1, 0, 0, -1, 0, 1, 1, 0, 0, -1, -1, 0, 1, 0, 0, -1, -1, 0, 0, 1};
//四个方向对应的左上右走和后退 
int book[45][45];
char map[45][45];
int n, m, sx, sy, ans1, ans2, flag;
void dfs(int x, int y, int dir){
	if(map[x][y] == 'E'){
		flag = 1;
		return;
	}
	int tx, ty;
	for(int i = 0; i < 4; ++i){
		tx = x + dnt[dir][i][0];
		ty = y + dnt[dir][i][1];
		if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
		if(map[tx][ty] == '#') continue;
		++ans1;
		dfs(tx, ty, (dir+i+3)%4);	//方向转换 
		if(flag) return;
		++ans1;
	}
}
void bfs(int x, int y){
	while(!q.empty()) q.pop();
	int tx, ty;
	tl.x = x, tl.y = y, tl.stp = 1;
	q.push(tl);
	while(!q.empty()){
		ft = q.front(); q.pop();
		if(map[ft.x][ft.y] == 'E'){
			ans2 = ft.stp;
			return;
		}
		for(int i = 0; i < 4; ++i){
			tx = ft.x + nt[i][0];
			ty = ft.y + nt[i][1];
			if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
			if(book[tx][ty] || map[tx][ty] == '#') continue;
			book[tx][ty] = 1;
			tl.x = tx, tl.y = ty, tl.stp = ft.stp+1;
			q.push(tl);
		}
	}
}
int main(){
	int t;
	scanf("%d", &t);
	for(int l = 1; l <= t; ++l)
	{
		scanf("%d %d", &m, &n);
		for(int i = 1; i <= n; ++i){
			scanf("%s", map[i]+1);
			for(int j = 1; j <= m; ++j){
				if(map[i][j] == 'S'){
					sx = i, sy = j;
				}
			}
		}
		ans1 = 1; flag = 0;
		dfs(sx, sy, 0);
		memset(book, 0, sizeof book);
		book[sx][sy] = 1;
		bfs(sx, sy);
		printf("%d %d\n", ans1, ans2);
	}
	return 0;
}
           

最近开补知识空白区吧，没时间偷懒了。