Skip to content

2850. Minimum Moves to Spread Stones Over Grid 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int minimumMoves(vector<vector<int>>& grid) {
    const int zeroCount = accumulate(grid.begin(), grid.end(), 0,
                                     [](int subtotal, const vector<int>& row) {
      return subtotal + ranges::count(row, 0);
    });
    if (zeroCount == 0)
      return 0;

    int ans = INT_MAX;

    for (int i = 0; i < 3; ++i)
      for (int j = 0; j < 3; ++j)
        if (grid[i][j] == 0)
          for (int x = 0; x < 3; ++x)
            for (int y = 0; y < 3; ++y)
              // Move a stone at (x, y) to (i, j).
              if (grid[x][y] > 1) {
                --grid[x][y];
                ++grid[i][j];
                ans = min(ans, abs(x - i) + abs(y - j) + minimumMoves(grid));
                ++grid[x][y];
                --grid[i][j];
              }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int minimumMoves(int[][] grid) {
    int zeroCount = 0;
    for (int[] row : grid)
      for (int cell : row)
        if (cell == 0)
          ++zeroCount;
    if (zeroCount == 0)
      return 0;

    int ans = Integer.MAX_VALUE;

    for (int i = 0; i < 3; ++i)
      for (int j = 0; j < 3; ++j)
        if (grid[i][j] == 0)
          for (int x = 0; x < 3; ++x)
            for (int y = 0; y < 3; ++y)
              if (grid[x][y] > 1) {
                --grid[x][y];
                ++grid[i][j];
                ans = Math.min(ans, Math.abs(x - i) + Math.abs(y - j) + minimumMoves(grid));
                ++grid[x][y];
                --grid[i][j];
              }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def minimumMoves(self, grid: list[list[int]]) -> int:
    if sum(row.count(0) for row in grid) == 0:
      return 0

    ans = math.inf

    for i in range(3):
      for j in range(3):
        if grid[i][j] == 0:
          for x in range(3):
            for y in range(3):
              if grid[x][y] > 1:
                grid[x][y] -= 1
                grid[i][j] += 1
                ans = min(ans, abs(x - i) + abs(y - j) +
                          self.minimumMoves(grid))
                grid[x][y] += 1
                grid[i][j] -= 1

    return ans