寻路专题系列（一）：你能到达终点吗？

[sunhengzhe]

假设你在一个 N*N 的迷宫里，初始位置为 [0, 0]。你只能往东南西北四个方向移动，如果能到达 [N-1, N-1] 位置返回 true，否则返回 false。

可以移动的位置标记为 点，不可移动的位置标记为 W。如：

.W...
...W.
W....

function testMaze(expected, maze){
  let actual = pathFinder(maze);
  Test.assertEquals(actual, expected, maze);
}

describe("Basic tests", function(){

testMaze(true,
`.W.
.W.
...`);

testMaze(false,
`.W.
.W.
W..`);

testMaze(true,
`......
......
......
......
......
......`);

testMaze(false,
`......
......
......
......
.....W
....W.`);

});

[sunhengzhe]

参考 寻路算法

class Graph {
	constructor(mazeStr) {
		const rows = mazeStr.split('\n');
		this.rows = rows;
		this.width = rows[0].length;
		this.height = rows.length;
	}

	getNeighbors(node) {
		const [ x, y ] = node;
		const neighbors = [];
		// 上
		if (y - 1 >= 0 && this.rows[y - 1][x] === '.') {
			neighbors.push([x, y - 1]);
		}
		// 右
		if (x + 1 < this.width && this.rows[y][x + 1] === '.') {
			neighbors.push([x + 1, y]);
		}
		// 下
		if (y + 1 < this.height && this.rows[y + 1][x] === '.') {
			neighbors.push([x, y + 1]);
		}
		// 左
		if (x - 1 >= 0 && this.rows[y][x - 1] === '.') {
			neighbors.push([x - 1, y]);
		}
		return neighbors;
	}
}

const maze = `....W
.WWW.
.....
W..W.
W..W.
.W.W.`;

function pathFinder(maze){
	const graph = new Graph(maze);

	const start = [0, 0];
	const end = [graph.width - 1, graph.height - 1];

	// 节点队列
	const frontier = [ start ];
	// 已被探索过的节点字典
	const visited = {
		[start]: true
	};

	while (frontier.length) {
		const current = frontier.shift();
		if (current.toString() === end.toString()) {
			return true;
		}
		
		const neighbors = graph.getNeighbors(current);
		for (const node of neighbors) {
			if (!visited[node]) {
				frontier.push(node);
				visited[node] = true;
			}
		}
	}

	return false;
}