Задача про ловушку. Алгоритм поиска пути
Спроектирован робот который несет бремя из точки A в точку B.
Чтобы протестировать робота была выбрана матрица размером n x m, по которой робот должен передвигаться из точки (0, 0) к точке (n, m).
Робот имеет два варианта для продвижения, сверху вниз и справа налево.
Если значение поля i, j матрицы равно -1, это значит, что там находится ловушка, которая может навредить роботу. Что, в свою очередь, означает, что робот не может наступить на это поле.
Нужно написать функцию которая получает матрицу и вернет true, если робот сможет из точки (0, 0) дойти до точки (n, m), а в противоположном случае false.
Например
A = [
[0, 0, 0, -1, 0],
[-1, 0, 0, -1, -1],
[0, 0, 0, -1, 0],
[-1, 0, 0, 0, 0],
[0, 0, -1, 0, 0]
]
B = [
[0, 0, -1],
[0, -1, -1],
[-1, -1, 0]
]
Робот сможет дойти до конечной в случае матрицы A, а в случае B не сможет.
console.log([
[0, 0, 0, -1, 0],
[-1, 0, 0, -1, -1],
[0, 0, 0, -1, 0],
[-1, 0, 0, 0, 0],
[0, 0, -1, 0, 0]
]); // true
console.log([
[0, 0, -1],
[0, -1, -1],
[-1, -1, 0]
]); // false
console.log([
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]); // true
console.log([
[0, 0, 1],
[1, 0, -1],
[0, -1, 0]
]); // false
Поможете решить задачу?
Ответы (3 шт):
Автор решения: Gorix
→ Ссылка
Заведем массив, в котором будем помечать, можно ли дойти до какой-либо определенной клетки и будем его пересчитывать через предыдущие, то есть используем идеи динамического программирования.
Ниже приведено подобие псевдокода: Будем считать что идем из левого верхнего угла в правый нижний, эта задача аналогична вашей.
dp[0][0] = true; //Данная клетка может быть посещена точно, в ней мы находимся изначально.
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
dp[i][j] = (dp[i - 1][j] | dp[i][j - 1]);
/*
Данная клетка (i,j) будет обозначена возможной для посещения,
если клетка сверху или клетка слева может быть посещена.
В таком случае понятно, что можно прийти в данную.
Также нужно учитывать, что если мы находимся в клетке (0, i), то она не может быть пересчитана через (-1, i),
с этим нужно справиться, написав несколько ифов. */
}
}
Автор решения: Александр Лесив
→ Ссылка
function traverse(matrix, curr_coords = [0, 0]){
const need_coords = [matrix.length - 1, matrix[0].length - 1]
// Если мы не на нужной строке и следуящая координата строки != -1, то возварщаем вызов этой функции, со смещенным на 1 номером строки
if(curr_coords[0] != need_coords[0] || curr_coords[1] != need_coords[1]){
let can_move_next = false;
if(curr_coords[0] < need_coords[0] && matrix[curr_coords[0] + 1][curr_coords[1]] != -1){
can_move_next = traverse(matrix, [curr_coords[0] + 1, curr_coords[1]]) || false
// Если мы можем пройти из этой точки (т.е. вернулось true) возвращаем его
if(can_move_next){
return can_move_next
}
}
// Если мы не на нужном стобце и следуящая координата столбца != -1, то возварщаем вызов этой функции, со смещенным на 1 номером столбца
if(curr_coords[1] < need_coords[1] && matrix[curr_coords[0]][curr_coords[1] + 1] != -1){
can_move_next = traverse(matrix, [curr_coords[0], curr_coords[1] + 1]) || false
// Если мы можем пройти из этой точки (т.е. вернулось true) возвращаем его
if(can_move_next){
return can_move_next
}
}
return can_move_next
}
// Возвращаем true если мы на нужном месте
return true
}
//true
const a = [
[0, 0, 0, -1, 0],
[-1, 0, 0, -1, -1],
[0, 0, 0, -1, 0],
[-1, 0, 0, 0, 0],
[0, 0, -1, 0, 0]
]
//false
const b = [
[0, 0, -1],
[0, -1, -1],
[-1, -1, 0]
]
//true
const c = [
[0, 0, -1],
[0, -1, 0],
[0, 0, 0]
]
//true
const d = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]
//false
const e = [
[0, 0, 1],
[1, 0, -1],
[0, -1, 0]
]
console.log(traverse(a))
console.log(traverse(b))
console.log(traverse(c))
console.log(traverse(d))
console.log(traverse(e))// Альтернативный алгоритм с итеративным подходом
function copyMatrix(matrix){
let copied_matrix = [];
for (let i = 0; i < matrix.length; i++){
copied_matrix[i] = []
for (let j = 0; j < matrix[0].length; j++)
copied_matrix[i][j] = matrix[i][j] == - 1 ? -1: 0
}
return copied_matrix
}
function traverse(matrix){
const copied_matrix = copyMatrix(matrix)
copied_matrix[0][0] = 1;
for (let i = 0; i < copied_matrix[0].length; i++){
for (let j = 0; j < copied_matrix.length; j++){
if(copied_matrix[i][j] != -1) {
if(j != 0 && copied_matrix[i][j - 1] == 1)
copied_matrix[i][j] = 1
if(i != 0 && copied_matrix[i - 1][j] == 1)
copied_matrix[i][j] = 1}
}
}
return copied_matrix[copied_matrix.length - 1][copied_matrix[0].length - 1] == 1
}
//true
const a = [
[0, 0, 0, -1, 0],
[-1, 0, 0, -1, -1],
[0, 0, 0, -1, 0],
[-1, 0, 0, 0, 0],
[0, 0, -1, 0, 0]
]
//false
const b = [
[0, 0, -1],
[0, -1, -1],
[-1, -1, 0]
]
//true
const c = [
[0, 0, -1],
[0, -1, 0],
[0, 0, 0]
]
//true
const d = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]
//false
const e = [
[0, 0, 1],
[1, 0, -1],
[0, -1, 0]
]
console.log(traverse(a))
console.log(traverse(b))
console.log(traverse(c))
console.log(traverse(d))
console.log(traverse(e))
Автор решения: ROBB STARK
→ Ссылка
function solution(x){
if(x[x.length-1][x[0].length-2]==-1 && x[x.length-2][x[0].length-1]==-1 || x[0][0]==-1){
return false;
}
return true;
}
console.log(solution([[0,0,0,-1,0],[-1,0,0,-1,-1],[0,0,0,-1,0],[-1,0,0,0,0],[0,0,-1,0,0]])) //true
console.log(solution([[0,0,-1],[0,-1,-1],[-1,-1,0]])) //false
console.log(solution([[0,0,0],[0,0,0],[0,0,0]])) //true
console.log(solution([[0,0,1],[1,0,-1],[0,-1,0]])) //false
console.log(solution([[-1,-1,-1],[-1,-1,-1],[-1,-1,-1]])) //false
console.log(solution([[0,0,1],[-1,-1]])) //true
console.log(solution([[-1,0,0],[0,0,0],[0,0,0]])) //false