博客

请帮他判断能否出走出迷宫，如果可能，则输出一共有多少种不同的走法（对于某种特定的走法，必须保证不能多次走到同一个位置）。如果不能走到出口，则输出impossible。每次走只能是上、下、左、右4个方向之一。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据首先输入2个整数n，m（0<n，m≤100），代表迷宫的高和宽，然后n行，每行m个字符，各字符的含义如下： ‘S’代表小明现在所在的位置；‘T’代表迷宫的出口；’#‘代表墙，不能走；’.’代表路，可以走。

输出格式:

对于每组测试，输出一共有多少种不同的走法，若不能走出则输出impossible。

输入样例:

4 4
S...
#..#
..#.
...T

输出样例:

4

#include<iostream>
#include<stack>
using namespace std;
char maze[100][100];
int vis[100][100];//判断是否已经走过
int n, m, dx, dy;
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
struct point {
	int x, y;
} p;
stack<point> path, temp;
int count1 = 0;
void dfs(int x, int y) {
	if (x == dx && y == dy) {
		cout << "******************路径" << ++count1 << "******************" << endl;
		while (!path.empty()) {
			point p1 = path.top();
			path.pop();
			temp.push(p1);
		}
		while (!temp.empty()) {
			point p1 = temp.top();
			temp.pop();
			path.push(p1);
			cout << "(" << p1.x << "," << p1.y << ")" << endl;
		}
		return;
	}
	if (x < 0 || x > n || y < 0 || y > m)	return;
	for (int i = 0; i < 4; i++) {
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		if (0 <= nx && nx < n && 0 <= ny && ny < m && (maze[nx][ny] == '.' || maze[nx][ny] == 'T') && vis[nx][ny] == 0) {
			vis[nx][ny] = 1;
			p.x = nx;
			p.y = ny;
			path.push(p);
			dfs(nx, ny);
			vis[nx][ny] = 0;
			path.pop();
		}
	}
}
int main() {
	while (cin >> n >> m) {
		count1 = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> maze[i][j];
				if (maze[i][j] == '.') vis[i][j] = 0;
				else if (maze[i][j] == '#') vis[i][j] = 1;
				else if (maze[i][j] == 'S') {
					p.x = i;
					p.y = j;
					path.push(p);
					vis[i][j] = 1;
				}
				if (maze[i][j] == 'T') {
					dx = i;
					dy = j;
					vis[i][j] = 0;
				}
			}
		}
		point a = path.top();
		dfs(a.x, a.y);
		if (count1 != 0) cout << count1 << endl;
		else cout << "impossible" << endl;
	}
	return 0;
}