Матч 44, Езда на машине (DriveCar)

Джон едет на машине по трехполосной дороге, разделенной на участки. Участки пронумерованы слева направо, начиная с нуля: 0, 1, 2, … . Полосы пронумерованы снизу к верху: 0, 1, 2. Сначала машина находится на средней полосе в самом левом участке (полоса 1, участок 0). Задача состоит в том, чтобы проехать на машине до последнего участка дороги, находясь на любой полосе, не ударившись в заграждения и не выехав за границы дороги.

За единицу времени автомобиль проезжает одну клетку. На каждом шаге автомобиль может либо остаться на той же полосе движения, или съехать по диагонали на соседнюю полосу. То есть находясь в состоянии (полоса, ячейка) = (i, j), он может попасть в состояние (i, j + 1), или в (i – 1, j + 1) при i > 0, или в (i + 1, j + 1) при i < 2.

Дорога задается массивом road, где road[i][j] описывает содержимое i - ой полосы j - ой ячейки. На клетки, обозначенные символом ‘#’ (заграждения), заезжать нельзя. Необходимо найти наименьшее количество смен полос, необходимое для преодоления всего маршрута. Если проезд невозможен, вернуть -1.

Класс: DriveCar

Метод: int minNumberOfDrifts(vector<string> road)

Ограничения: road содержит в точности 3 строки равной длины, road[i] содержит от 1 до 50 символов ‘.’, ‘#’, самая левая ячейка средней полосы содержит ‘.’.

Вход. Массив road, описывающий состояние трехполосной дороги.

Выход. Наименьшее количество смен полос, необходимое для преодоления всего маршрута. Если проезд невозможен, вернуть -1.

Пример входа

road

{"....",

"....",

"...."}

{"#.###.##",

".#.#.#.#",

"###.###."}

{"..#....#..#.#...#..",

"...#.#...#.#..#..#.",

".##..........#...#."}

Пример выхода

0

7

5

РЕШЕНИЕ

динамическое программирование

Заведем массив d[3][51], где в d[i][j] будем хранить наименьшее количество смен полос, которое следует совершить для прибытия в участок j полосы i. Изначально положим d[i][j] = ¥, d[1][0] = 0 (с полосы 1 участка 0 стартует Джон). Последовательно будем вычислять значения ячеек массива d, соответствующих j - му участку, используя значения ячеек d по (j – 1) - му участку (j = 1, 2, …, n = road[0].size()–1). Используем следующие правила при движении в точку (i, j) (полоса i, участок j):

1. Если road[i][j] = '.', то можно двигаться прямо из точки (i, j – 1): d[i][j] = d[i][j – 1];

2. Если road[i][j] = '#', то ничего не делаем (остается d[i][j] = ¥).

3. Если в клетку (i, j) можно попасть из верхней полосы предыдущего участка – клетки (i – 1, j – 1), то положим d[i][j] = min(d[i][j], d[i – 1][j – 1] + 1).

4. Если в клетку (i, j) можно попасть из нижней полосы предыдущего участка – клетки (i + 1, j – 1), то положим d[i][j] = min(d[i][j], d[i + 1][j – 1] + 1).

Результатом res будет наименьшее значение среди d[n][0], d[n][1], d[n][2], так как Джон может остановиться в любой полосе n - го участка. Если res = ¥, то установим res = -1, в этом случае пути из начальной позиции до конечного участка не существует.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <memory>

using namespace std;

int d[3][51];

class DriveCar

{

public:

int minNumberOfDrifts(vector<string> road)

{

int i,j,res,n=(int)road[0].size()-1;

memset(d,0x3F,sizeof(d)); d[1][0] = 0;

for(j=1;j<=n;j++)

for(i=0;i<3;i++)

{

if (road[i][j] == '.') d[i][j] = d[i][j-1];

if (road[i][j] == '#') continue;

if ((i>0) && (road[i-1][j-1] == '.'))

d[i][j] = min(d[i][j],d[i-1][j-1]+1);

if ((i<2) && (road[i+1][j-1] == '.'))

d[i][j] = min(d[i][j],d[i+1][j-1]+1);

}

res = min(min(d[0][n],d[1][n]),d[2][n]);

if (res == 0x3F3F3F3F) res = -1;

return res;

}

};