问题标题: 酷町堂：5012 走迷宫

5012   走迷宫

经验值：800 时间限制：1000毫秒

题目描述 Description

给出一个n行m列的二维迷宫，‘S’表示起点，‘T’ 表示终点，’#’ 表示墙壁，’.’ 表示平地。你需要从 ‘S’ 出发走到 ‘T’，每次只能上下左右走动，并且不能走出地图的范围以及不能走到墙壁上。请你计算出走到终点需要走的最少步数。

输入描述 Input Description

第一行输入n, m表示迷宫大小。
接下来输入n行字符串表示迷宫，每个字符串长度为m。（地图保证有且仅有一个终点，一个起始点）

输出描述 Output Description

输出走到终点的最少步数，如果不能走到终点输出−1

样例输入 Sample Input

2 3 S.# ..T

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

n,m<=15

 

 

错误代码，输出1061109567

//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, sx, sy, ex, ey;
int dir[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
bool G[20][20], vis[20][20];
int minn = 0x3f3f3f3f;
char s[20][20];
void dfs(int x, int y, int t) {
	if (x == ex && y == ey) {
		if (t < minn) {
			minn = t;
		}
		return ;
	}
	for (int i = 0; i < 4; i ++) {
		int nx = x + dir[i][0], ny = y + dir[i][1];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && G[nx][ny]) {
			vis[nx][ny] = true;
			dfs(nx, ny, t + 1);
			vis[nx][ny] = false;
		}
	}
}
int main() {
//	freopen ("题目名.in", "r", stdin);
//	freopen ("题目名.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			cin >> s[i][j];
			if (s[i][j] == 'S') {
				sx = i;
				sy = j;
			}
			if (s[i][j] == 'T') {
				ex = i;
				ey = j;
			}
			if (s[i][j] == '.') {
				G[i][j] = true;
			}
		}
	}
	vis[sx][sy] = true;
	dfs(sx, sy, 1);
	vis[sx][sy] = false;
	cout << minn;
//	fclose (stdin);
//	fclose (stdout);
	return 0;//好习惯！
}

这种题太ex了

张恩泽在2021-06-15 12:39:16追加了内容

help!!