# 16ms c++, fastest? improvement of StefanPorsche's code

• /* firstly, stefan has done great job optimizing by reducing empty land. link:
https://leetcode.com/discuss/74453/36-ms-c-solution

however in processing each building, he creates whole board to store distance:
auto dist = grid;

which is replaced by one variable level in my code. the running time is reduced to 16ms from 36ms. */

``````class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
int m=grid.size(), n=grid[0].size(), mark=0, ans;

vector<vector<int>> dist(m, vector<int>(n, 0));

int dx[4] = {0, 1, 0, -1}; // up, right, down, left
int dy[4] = {1, 0, -1, 0};

for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
if (grid[j][i]==1) {
vector<pair<int, int>> bfs(1, make_pair(j, i)), bfs2;
int level=1;
ans=INT_MAX;
while (!bfs.empty()) {
for (auto p : bfs) {
int y=p.first, x=p.second;
for (int d=0; d<4; d++) {
int nx=x+dx[d], ny=y+dy[d];
if (0<=nx && nx<n && 0<=ny && ny<m && grid[ny][nx]==mark) {
grid[ny][nx] = mark-1;
dist[ny][nx] += level;
ans = min(ans, dist[ny][nx]);
bfs2.push_back(make_pair(ny, nx));
}
}
}
level++;
std::swap(bfs, bfs2);
bfs2.clear();
}
mark -= 1;
}
return ans==INT_MAX ? -1 : ans;
}
};``````

• I don't know why my code doesn't produce the correct results. So far, I think it's quite similar to yours. Thanks

``````class Solution {
vector<pair<int, int>> vd{ make_pair<int, int>(-1, 0), make_pair<int, int>(1, 0), make_pair<int, int>(0, 1), make_pair<int, int>(0, -1) };
public:
int shortestDistance(vector<vector<int>>& grid) {
if (grid.empty())
return 0;

int row = grid.size(), col = grid[0].size();

pair<int, int> t;
int walk = 0, res=INT_MAX;
vector<vector<int>> dist(row, vector<int>(col, 0));

for (int r = 0; r < row; r++)
for (int c = 0; c < col; c++)
{

if (grid[r][c] == 1)
{
int level = 1;
t.first = r;
t.second = c;

queue<pair<int, int>> q, nextQ;
res=INT_MAX;

q.push(t);

while (!q.empty())
{
t = q.front();
int rn, cn;
q.pop();
for (int i = 0; i < vd.size(); i++)
{
rn = t.first + vd[i].first;
cn = t.second + vd[i].second;

if (rn < 0 || rn >= row || cn<0 || cn >= col || grid[rn][cn]>0)
{
continue;
}

if (grid[rn][cn] == walk)
{
grid[rn][cn] = walk - 1;
dist[rn][cn] = level + 1;
res = min(res, dist[rn][cn]);

pair<int, int> nei;
nei.first = rn;
nei.second = cn;
nextQ.push(nei);
}
}
level++;
swap(q,nextQ);
}
walk--;
}

}

if (res == INT_MAX)
return -1;
else
return res;
}
};``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.