站外题(一本通1215)

迷宫

时间限制: 1000 ms 内存限制: 65536 KB

【题目描述】

一天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

我的 TLE 0分代码：

#include<bits/stdc++.h>
using namespace std;
int mv[2][4] = {{1, -1, 0, 0}, {0, 0, 1, -1}};
bool vis[100][100];
int hb, lb, n;
bool dfs(int i, int j) {
	for(int k = 0; k <= 3; k++) {
		int x = i + mv[0][k];
		int y = j + mv[1][k];
		if(x >= 0 && x <= n && y >= 0 && y <= n && !vis[x][y]) {
			vis[x][y] = 1;
			if(x == hb && y == lb) {
				return true;
			}
			if(dfs(x, y))
				return true;
			vis[x][y] = 0;
		}
	}
	return false;
}
int main() {
	int k, ha, la;
	char c;
	scanf("%d", &k);
	while(k--) {
		memset(vis, 1, sizeof(vis));
		scanf("%d\n", &n);
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				scanf("%c", &c);
				if(c == '.')
					vis[i][j] = 0;
			}
			getchar();
		}
		scanf("%d%d%d%d", &ha, &la, &hb, &lb);
		vis[ha][la] = 1;
		if(dfs(ha, la))
			printf("YES\n");
		else
			printf("NO\n");
	}
}

求大佬帮助