Не уверен, является ли это актуальным или нет, но проблема, которую я пытаюсь решить,
~~~~~~~~~~~~~ Кратчайшее расстояние от всех зданий ~~~~~~~~~~~~~~~
Вы хотите построить дом на пустой земле, которая достигает всех зданий на кратчайшем расстоянии. Вы можете двигаться только вверх, вниз, влево и вправо. Вам дана двумерная сетка значений 0, 1 или 2, где:
Каждый 0 обозначает пустую землю, которую вы можете свободно пройти.
Каждый 1 обозначает здание, через которое вы не можете пройти.
Каждые 2 обозначают препятствие, через которое вы не можете пройти.
Найдите наименьшее расстояние от пустой земли, которая может получить доступ ко всем зданиям
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~
Хотя мое решение работает корректно на небольших входах, оно из-за большой временной сложности рассчитывается по тайм-ауту.
Однако я не уверен в точной временной сложности этого решения и хочу правильно понять, какова временная сложность этого решения, чтобы я мог попытаться улучшить его, если это возможно.
Я почти уверен, что временная сложность внешнего цикла равна O (MN) (M - это общее количество строк, а N - общее количество столбцов), потому что мы зацикливаемся по всей позиции сетки, но я я не уверен в сложности времени рекурсивного метода shortDist. Является ли это также O (MN), потому что в худшем случае оно коснется каждой позиции сетки и, следовательно, общая временная сложность этого решения будет O (M ^ 2 * N ^ 2) или это что-то еще, если так, то было бы замечательно, если бы кто-то мог объяснить мне об этом.
Мое решение -
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;
}
};