Поиск пути в матрице с++

Всем привет :)

Вопрос такой : Имеется матрица вида

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;
}

Заранее спасибо :)