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


  • 8
    W

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

  • 0
    C

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

  • 0
    E
    This post is deleted!

Log in to reply
 

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