以下递归代码的时间复杂度是多少

不确定是否相关,但我想解决的问题是

每一个0代表一块你可以自由通行的空地。 每两个标记一个你不能通过的障碍。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

虽然我的解决方案在小的输入上工作正常,但由于时间复杂度很大,它在较大的输入上超时。

但是,我不确定这个解决方案的确切时间复杂度,希望正确理解这个解决方案的时间复杂度是什么,以便我可以尝试改进它,如果可能的话。

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {

        vector<std::pair<int,int>> dir = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        // pair(row, col) -> distance
        map<std::pair<int,int>, int> cache;
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false)); // to check if we have already visited that location on the grid
        int minDist = INT_MAX;
        int maxCount =0;
        // Finding number of 1's
        for(int i =0; i< grid.size(); i++)
        {
            for(int y =0; y < grid[0].size(); y++)
            {
                if(grid[i][y] == 1)
                {
                    maxCount++;
                }
            }
        }
        // For each 0 find the distance of each 1's and their count
        // if the count of 1's is less than the number of 1's in the
        // grid that grid position is not an acceptable pos
        for(int i =0; i< grid.size(); i++)
        {
            for(int y =0; y < grid[0].size(); y++)
            {
                if(grid[i][y] == 0)
                {
                    shortDist(grid, cache, dir, visited, i, y, 0);
                    int dist =0;
                    int count = cache.size();// number of 1's
                    if(count == maxCount)
                    {
                        // if we are here it implies that the empty land space have path to all the buildings
                        for(auto iter = cache.begin(); iter != cache.end(); iter++)
                        {
                            dist += iter->second;
                        }
                        if(dist < minDist)
                        {
                            minDist = dist;
                        }
                    }
                    cache.clear();
                }       
            }
        }

        return minDist == INT_MAX ? -1 : minDist;

    }

    void shortDist(vector<vector<int>>& grid, map<std::pair<int,int>, int>& cache, vector<std::pair<int,int>>& dir, vector<vector<bool>>& visited, int row, int col, int dist)
    {
        if(row < 0 || col < 0 || row >= grid.size() || col >= grid[0].size())
        {
            return;
        }
        if(grid[row][col] == 2)
        {
            return;
        }
        if(grid[row][col] == 1)
        {
            auto found = cache.find(make_pair(row, col));
            if(found == cache.end())
            {
                cache[(make_pair(row, col))] = dist;
            }
            else
            {
                found->second = min(found->second, dist);
            }

            return;
        }

        if(visited[row][col])
        {
            return;
        }

        visited[row][col] = true;
        for(int i =0; i < dir.size(); i++)
        {
            int newRow = row + dir[i].first;
            int newCol = col + dir[i].second;
            shortDist(grid, cache, dir, visited, newRow, newCol, dist+1);
        }
        visited[row][col] = false;
    }
};