题解 | 迷宫寻路

#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int n, m;
char c[101][101];
//0表示未确定, -1表示不能，1表示可以,这个cache可以保证每个节点只遍历一遍 
int cache[101][101] = {0};
int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
//注意要记录轨迹，必然会死循环
int vis[101][101] = {0};

//记录一下c++的bool的使用细节
//1. int支持直接作为条件使用if (int)，对于int != 0都是true(包括int < 0)
//2. 对于int & bool是转int运算， int && bool是转bool运算
//3. cout << bool是输出1 / 0
bool dfs(int i, int j) {
	if (i == n && j == m) return c[i][j] == '.';
	if (cache[i][j]) return cache[i][j] > 0; 
	bool ans = false;
	for (int k = 0; k < 4; k++) {
		int x = i + direction[k][0];
		int y = j + direction[k][1];
		if (x <= n && 1 <= x && 1 <= y && y <= m && c[x][y] != '#' && !vis[x][y]) {
			vis[x][y] = 1;
			ans = ans || dfs(x, y);
		}
	}
	cache[i][j] = ans ? 1 : -1;
	return ans; 
}

int main() {
	
	cin >> n >> m;
	for (int i = 1;i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> c[i][j];   
		}
	}
	cout << (dfs(1, 1) ? "Yes" : "No") << endl;
}