Всем привет :)
Вопрос такой : Имеется матрица вида
4 7
...*...
.......
..###..
...@...
где '@' - шарик ,который нужно переместить в '*'.Символ '#' - стена(через них ходить нельзя),через символ '.' ходить можно. Задача заключается в том чтобы найти количество минимальных путей из @ в *.(например в данном примере кол-во минимальных путей == 6)
Мой алгоритм такой: сначала ищу всевозможные пути и записываю их в **path(путем будет 1,2,3,4,5...*)
После этого с помощью рекурсии иду с конца(с '*') до начала и на каждой итерации рекурсии проверяю есть ли еще какой нибудь путь,если есть то global_count_of_ways++ .
Проблема в том что это очень долго. При больших N(строки) и M(столбцы) вылезает time limit.
Вот код,который я написал
#include <iostream>
#include <queue>
using namespace std;
struct way {
int visited;
int count_way;
};
/* нахождение пути*/
void find_road(int n, int m, int row, int col, char** lab, int** visited, way** path, queue<int>& plan) {
if (!visited[row][col]) {
/* проверяем не вышли ли мы за границы лабиринта, есть ли клетка
в массиве посещенных и можно ли через нее пройти*/
if ((row + 1) < n && (row + 1) >= 0 && !visited[row + 1][col] &&
(lab[row + 1][col] == '.' || lab[row + 1][col] == '*')) {
path[row + 1][col].visited = path[row][col].visited + 1;
path[row + 1][col].count_way += path[row][col].count_way;
plan.push(row + 1);
plan.push(col);
}
if ((row - 1) < n && (row - 1) >= 0 && !visited[row - 1][col] &&
(lab[row - 1][col] == '.' || lab[row - 1][col] == '*')) {
path[row - 1][col].visited = path[row][col].visited + 1;
path[row - 1][col].count_way += path[row][col].count_way;
plan.push(row - 1);
plan.push(col);
}
if ((col + 1) < m && (col + 1) >= 0 && !visited[row][col + 1] &&
(lab[row][col + 1] == '.' || lab[row][col + 1] == '*')) {
path[row][col + 1].visited = path[row][col].visited + 1;
path[row][col + 1].count_way += path[row][col].count_way;
plan.push(row);
plan.push(col + 1);
}
if ((col - 1) < m && (col - 1) >= 0 && !visited[row][col - 1] &&
(lab[row][col - 1] == '.' || lab[row][col - 1] == '*')) {
path[row][col - 1].visited = path[row][col].visited + 1;
path[row][col - 1].count_way += path[row][col].count_way;
plan.push(row);
plan.push(col - 1);
}
visited[row][col] = 1; /* отмечаем клетку в которой побывали */
}
}
int main() {
int n, m, x_start, y_start, x_end, y_end, x, y;
queue <int> plan;
cin >> n; cin >> m;
char** lab = new char*[n];
int** visited = new int*[n];
way** path = new way*[n];
for (int i = 0; i < n; i++) {
lab[i] = new char[m]; /* массив для хранения лабиринта */
visited[i] = new int[m]; /* массив для хранения информации о посещении клеток*/
path[i] = new way[m]; /* массив для хранения найденных путей */
for (int j = 0; j < m; j++) {
visited[i][j] = 0;
path[i][j].visited = -1;
path[i][j].count_way = 0;
cin >> lab[i][j];
if (lab[i][j] == '@') { /* находим начало пути*/
x_start = i;
y_start = j;
plan.push(i); /* заносим начальную клетку */
plan.push(j); /* в план посещения */
path[i][j].visited = 1;
path[i][j].count_way = 1;
}
else if (lab[i][j] == '*') { /* находим конечную точку */
x_end = i;
y_end = j;
}
}
}
while (!plan.empty()) { /* пока очередь посещения клеток непустая*/
x = plan.front();
plan.pop();
y = plan.front();
plan.pop();
find_road(n, m, x, y, lab, visited, path, plan); /* продолжаем поиск пути*/
}
cout << path[x_end][y_end].count_way % 1000000007 << endl;
return 0;
}
Заранее спасибо :)
1
), затем выполняем итерационный процесс: число способов попасть в некоторую ячейку равно сумме числа способов попасть в предшествующие ей (на кратчайшем пути). В итоге время выполнение составит порядка "О большое" от размера матрицы.k
, гдеk
- длина кратчайшего пути (её можно посчитать заранее однократным поиском в ширину). Вы получите как раз в ячейке(i,j)
этой матрицы число способов добраться изi
вj
, только беда в том, что у вас матрица смежности будет иметь размерыN*M x N*M
. И тот способ, который я описал выше, он как раз чем-то похож на работу с разряжёнными матрицами, как будто бы мы выполняли умножение линейным методом, а не бинарным.