3 3
2 1 1
1 1 0
0 1 1

4

3 3
2 1 1
0 1 1
1 0 1

-1

1 2
0 2

0

from collections import deque

class Solution:
    def orangesRotting(self, grid):
        n, m = len(grid), len(grid[0])
        queue = deque()
        fresh_count = 0

        # 遍历网格，初始化队列和新鲜橘子计数
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 2:
                    queue.append((i, j, 0))  # (行, 列, 时间)
                elif grid[i][j] == 1:
                    fresh_count += 1

        # 如果没有新鲜橘子，返回 0
        if fresh_count == 0:
            return 0

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        minutes = 0

        # BFS 遍历
        while queue:
            x, y, minutes = queue.popleft()

            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:
                    grid[nx][ny] = 2  # 腐烂橘子
                    queue.append((nx, ny, minutes + 1))
                    fresh_count -= 1

        return -1 if fresh_count > 0 else minutes

# 读取输入
if __name__ == "__main__":
    n, m = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(n)]
    
    solution = Solution()
    print(solution.orangesRotting(grid))

import java.util.*;

public class Main {
    public class Solution {
        public int orangesRotting(int[][] grid) {
            int n = grid.length, m = grid[0].length;
            Queue<int[]> queue = new LinkedList<>();
            int freshCount = 0;

            // 初始化队列和新鲜橘子数量
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 2) {
                        queue.offer(new int[]{i, j, 0}); // (行, 列, 时间)
                    } else if (grid[i][j] == 1) {
                        freshCount++;
                    }
                }
            }

            // 如果没有新鲜橘子，直接返回 0
            if (freshCount == 0) {
                return 0;
            }

            int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            int minutes = 0;

            // BFS 遍历
            while (!queue.isEmpty()) {
                int[] current = queue.poll();
                int x = current[0], y = current[1];
                minutes = current[2];

                for (int[] dir : directions) {
                    int nx = x + dir[0], ny = y + dir[1];

                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;  // 变成腐烂橘子
                        queue.offer(new int[]{nx, ny, minutes + 1});
                        freshCount--;
                    }
                }
            }

            return freshCount > 0 ? -1 : minutes;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] grid = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        Main main = new Main();
        Solution solution = main.new Solution();
        System.out.println(solution.orangesRotting(grid));
    }
}

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        queue<tuple<int, int, int>> q;
        int freshCount = 0;

        // 遍历网格，初始化队列和新鲜橘子数量
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) {
                    q.push({i, j, 0}); // (行, 列, 时间)
                } else if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }

        // 如果没有新鲜橘子，直接返回 0
        if (freshCount == 0) return 0;

        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int minutes = 0;

        // BFS 遍历
        while (!q.empty()) {
            auto [x, y, time] = q.front();
            q.pop();
            minutes = time;

            for (auto [dx, dy] : directions) {
                int nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    q.push({nx, ny, minutes + 1});
                    freshCount--;
                }
            }
        }

        return freshCount > 0 ? -1 : minutes;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    Solution solution;
    cout << solution.orangesRotting(grid) << endl;

    return 0;
}