Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
BFS or DFS solution in Clear category for [old] Can You Pass? by Sim0000
"use strict";
function canPass(matrix, first, second) {
let ysize = matrix.length, xsize = matrix[0].length;
let visited = Array(ysize);
for(let y = 0; y < ysize; y++) visited[y] = Array(xsize).fill(false);
let [gy, gx] = second; // goal
let c = matrix[gy][gx];
let stack = [];
stack.push(first);
while(stack.length > 0){
let [y, x] = stack.shift(); // BFS
//let [y, x] = stack.pop(); // DFS
if(y < 0 || ysize <= y || x < 0 || xsize <= x || visited[y][x] || matrix[y][x] != c) continue;
if(y == gy && x == gx) return true; // goal
visited[y][x] = true;
stack.push([y - 1, x]);
stack.push([y + 1, x]);
stack.push([y, x - 1]);
stack.push([y, x + 1]);
}
return false;
}
var assert = require('assert');
if (!global.is_checking) {
// These "asserts" are used for self-checking and not for an auto-testing
assert.equal(canPass([[0, 0, 0, 0, 0, 0],
[0, 2, 2, 2, 3, 2],
[0, 2, 0, 0, 0, 2],
[0, 2, 0, 2, 0, 2],
[0, 2, 2, 2, 0, 2],
[0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2]],
[3, 2], [0, 5]), true)
assert.equal(canPass([[0, 0, 0, 0, 0, 0],
[0, 2, 2, 2, 3, 2],
[0, 2, 0, 0, 0, 2],
[0, 2, 0, 2, 0, 2],
[0, 2, 2, 2, 0, 2],
[0, 0, 0, 0, 0, 2],
[2, 2, 2, 2, 2, 2]],
[3, 3], [6, 0]), false)
console.log("Coding complete? Click 'Check' to earn cool rewards!");
}
Aug. 6, 2018
Comments: