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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
#include <queue>
using namespace std;
int n, m, k, q, w, a[1002][1002];
queue<pair<int, int>> dp2;
int main() {
	cin >> m >> n;
	for (int i = 0; i < n; i++)
		for (int t = 0; t < m; t++) {
			cin >> a[i][t];
			if (a[i][t] == 1)	dp2.push({ i,t });
		}
	for (int i = 0;; i++) {
		queue<pair<int, int>> dp1;
		while (!dp2.empty()) {
			q = dp2.front().first;
			w = dp2.front().second;
			if (w + 1 < m && !a[q][w + 1]) {
				dp1.push({ q,w + 1 });
				a[q][w + 1]++;
			}
			if (q + 1 < n && !a[q + 1][w]) {
				dp1.push({ q + 1,w });
				a[q + 1][w]++;
			}
			if (w >= 1 && !a[q][w - 1]) {
				dp1.push({ q,w - 1 });
				a[q][w - 1]++;
			}
			if (q >= 1 && !a[q - 1][w]) {
				dp1.push({ q - 1,w });
				a[q - 1][w]++;
			}
			dp2.pop();
		}
		if (dp1.empty()) {
			k = i;
			break;
		}
		dp2 = dp1;
	}
	for (int i = 0; i < n; i++)
		for (int t = 0; t < m; t++)
			if (!a[i][t]) {
				k = -1;
				break;
			}
	cout << k << endl;
}