317

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        int ans = INT_MAX;
        int total[rows][cols];
        memset(total, 0, sizeof total);

        int itr = 0;
        int dir[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        for(int i=0; i<rows; i++)
            for(int j=0; j<cols; j++){
                if(grid[i][j] == 1){
                    int currMin = INT_MAX;
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    auto dist = grid;
                    while(!q.empty()){
                        auto p = q.front(); q.pop();
                        for(int k=0; k<4; k++){
                            int nextX = p.first+dir[k][0], nextY = p.second+dir[k][1];
                            if(nextX < 0 || nextX >= rows || nextY < 0 || nextY >= cols || grid[nextX][nextY] != itr)
                                continue;
                            dist[nextX][nextY] = dist[p.first][p.second]+1;
                            total[nextX][nextY] += dist[nextX][nextY]-1;
                            grid[nextX][nextY]--;
                            q.push({nextX, nextY});
                            currMin = min(currMin, total[nextX][nextY]);
                        }
                    }
                    itr--;
                    ans = currMin;
                }
            }

        return (ans==INT_MAX) ? -1 : ans;
    }
};