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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 50 + 5;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,1,0,-1};
const int INF = 0x3f3f3f3f;
int n, m, a[N][N], vis[N][N], c[N*N], idx = 1, ans = INF;
// a存储输入，vis存储连同块（结点）编号，c存储结点颜色
bool bvis[N*N]; // 用于BFS判断结点是否已访问
vector<vector<int>> G; // 邻接表
struct Node {
int idx, step;
};
// 检查是否在界线内
bool check(int x, int y) {
return 1 <= x && x <= n && 1 <= y && y <= m;
}
// 判断黑连通块并建图
bool dfs1(int x, int y) {
if (vis[x][y] > 0) return false; // 不是黑连通块
// 与白连通块接壤，建边
if (a[x][y] == 0) {
if (vis[x][y] < 0) { // 重边不影响BFS,不用判重
G[idx].push_back(-vis[x][y]);
G[-vis[x][y]].push_back(idx);
}
return false;
}
vis[x][y] = idx; // 访问标记，也是结点编号
c[idx] = 1; // 结点颜色为黑（1）
// 继续DFS
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (check(nx, ny) && vis[nx][ny] <= 0) dfs1(nx, ny);
}
return true; // 是黑连通块
}
// 判断白连通块并建图
bool dfs0(int x, int y) {
if (vis[x][y] < 0) return false;
// 与黑连通块接壤，建边
if (a[x][y] == 1) { // 重边不影响BFS,不用判重
if (vis[x][y] > 0) {
G[idx].push_back(vis[x][y]);
G[vis[x][y]].push_back(idx);
}
return false;
}
vis[x][y] = -idx; // 访问标记，也是结点编号
// 结点颜色为白（0）。不做操作，因为 c 初始值为 0
// 继续DFS
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (check(nx, ny) && vis[nx][ny] >= 0) dfs0(nx, ny);
}
return true;
}
// 求无权图上的最短路
void bfs(int k) {
memset(bvis, 0, sizeof(bvis));
int t = -INF; // 存储到各个结点的最短路的最大值
Node tmp;
queue<Node> q;
q.push({k, 0});
bvis[k] = true;
while (!q.empty()) {
tmp = q.front();
q.pop();
t = max(t, (c[tmp.idx] ? tmp.step+1 : tmp.step)); // 如果最短路终点为黑色（1），则步数+1
for (auto i : G[tmp.idx]) {
if (!bvis[i] && i != idx) {
q.push({i, tmp.step+1});
bvis[i] = true;
}
}
}
ans = min(ans, t);
}
// 求出从各点出发到所有点的最短路的最大值的最小值
void solve() {
for (int i = 1; i < idx; i++) bfs(i);
cout << ans << endl;
}
// 读入数据并建图
void init() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cin >> a[i][j];
G.resize(2500+1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (a[i][j]) if (dfs1(i, j)) idx++;
if (!a[i][j]) if (dfs0(i, j)) idx++;
}
}
int main() {
#ifdef LOCAL
freopen("E_2.in", "r", stdin);
#endif
IOS
init();
solve();
// 遍历结点颜色
// for (int i = 1; i < idx; i++) cout << c[i] << ' ';
// cout << endl << endl;
// 遍历访问数组
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) cout << vis[i][j] << ' ';
// cout << endl;
// } cout << endl;
// 遍历邻接表
// for (int i = 1; i < idx; i++) {
// cout << i << ": ";
// for (auto j : G[i]) cout << j << ' ';
// cout << endl;
// }
return 0;
}
|
