迷宫

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 17560 通过数: 5084

【题目描述】

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。

【输入】

第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 ≤ n ≤ 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。

【输出】

k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。

【输入样例】

2
3
.##
..#

..

0 0 2 2
5
.....

.#

..#..

..

...#.
0 0 4 0

【输出样例】

YES
NO

题解

前置知识：递归是靠栈运行的

migong[][]记录'.''#'

状态：

设为第a行，第b列

转移：

向上下左右分别移动，若满足(此格子为'.'，并且在迷宫内(即0<=行<n,0<=列<n)),则可以转移到这个格子

我们用x[4] = {0,0，1,-1}， y[4] = {1,-1,0,0}来表示向上下左右移动。比如a+x[0]表示行不加不减，b+y[0]表示列加一，也就是向东移动

回溯：

当前格子migong[a][b]可以向东转移一步，转移时我们令migong[a+x[0]][b+y[0]]变成'#',这样从migong[a+x[0]][b+y[0]]继续转移时，就不会再转移到migong[a+x[0]][b+y[0]]了。
然后migong[a+x[0]][b+y[0]]一直转移转移。。转移移移移，移完了
然后当前格子migong[a][b]不向东转移，而向西转移（即转移到migong[a+x[1]][b+y[1]]）之前，
我们再让migong[a+x[0]][b+y[0]]变回'.',
这样migong[a+x[1]][b+y[1]]再继续转移时就不会被曾经移到过migong[a+x[0]][b+y[0]]而影响，也就是在migong[a+x[1]][b+y[1]]的递归过程中可以转移到migong[a+x[0]][b+y[0]]。
但是，问题来了这样是TLE的!
你仔细想想，migong[a+x[1]][b+y[1]]既然又转移到了migong[a+x[0]][b+y[0]]，那为啥不直接在migong[a][b]时直接转移到migong[a+x[0]][b+y[0]]？？我们回溯让migong[a+x[0]][b+y[0]]变回'.'其实不应该

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int n;
char migong[105][105];
int ha , la , hb , lb;
int x[4] = {-1 , 1 , 0 , 0} , y[4] = {0 , 0 , -1 , 1}; 
int t;
int QR(){
	char c = getchar();
	while(c < '0' || c > '9'){
		c = getchar();
	}
	int res = 0;
	while(c <= '9' && c >= '0'){
		res *= 10;
		res += c  - '0';
		c = getchar();
	}
	return res;
}

void dfs(int a , int b)
{
	if(t == 1)	return;
	if (a == hb && b == lb)
	{
		printf("YES
");
		t = 1;
		return;
	}
	for (int i = 0 ; i <= 3 ; i++)
	{
		if(a + x[i] >= 0 && b + y[i] >= 0 && a + x[i] < n && b + y[i] < n && migong[a + x[i]][b + y[i]] == '.' )
		{
			migong[a + x[i]][b + y[i]] = '#';
			dfs(a + x[i] , b + y[i]);
//			migong[a + x[i]][b + y[i]] = '.';  //不回溯， 
		}
	}
}

int main()
{
	int k;
	k = QR();
	while(k--)
	{
		t = 0; 
		n = QR();
		for (int i = 0 ; i < n ; i++)
		{
			for (int j = 0 ; j < n ; j++)
			{
				cin >> migong[i][j];
			}
		}
		ha = QR();
		la = QR();
		hb = QR();
		lb = QR();
		if (migong[ha][la] == '#'){
			printf("NO
");
			continue;
		}
		migong[ha][la] = '#';
		dfs(ha , la);
		if (t == 0)
			printf("NO
");
	}
	return 0;
}