C++ BFS Short Solution


  • 0
    K

    '''

     int shortestDistance(vector<vector<int>> grid) {
     int m = grid.size(), n = grid[0].size();                
     auto total = grid;
     int walk = 0, mindist, delta[] = { 0, 1, 0, -1, 0 };
     for (int i = 0; i<m; ++i) {
         for (int j = 0; j<n; ++j) {
    	if (grid[i][j] == 1) {
    		vector<vector<bool>> visited(m, vector<bool>(n, 0));
    		int dist1 = 1;
    		mindist = -1;
    		queue<pair<int, int>> q;
    		q.emplace(i, j);
    		while (q.size()) {
    			int size = q.size();
    			while (size) {
    			auto ij = q.front();
    			q.pop();
    			size--;
    			for (int d = 0; d < 4; ++d) {
    				int i = ij.first + delta[d];
    				int j = ij.second + delta[d + 1];
    				if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == walk && !visited[i][j]) {
    					grid[i][j]--;
    					visited[i][j] = true;
    					total[i][j] += dist1;
    					q.emplace(i, j);
    					if (mindist < 0 || mindist > total[i][j])
    					        mindist = total[i][j];
    					}
    				}
    			}
    		dist1++;
    		}
    	walk--;
    	}
         }
      }
      return mindist;
    }
    

    '''


Log in to reply
 

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