Problem Statement
$\hspace{15pt}$牛可乐有 $n \times m$ 个砖块排布成 $n$ 行 $m$ 列的矩阵，我们使用 $(i,j)$ 表示矩阵中从上往下数第 $i$ 行和从左往右数第 $j$ 列的砖块。如下左图就是一个 $6$ 行 $6$ 列的矩阵。有的砖块能被敲碎，为了便于辨认，我们使用灰色绘制它们；有的砖块不能被敲碎，我们使用蓝色斜线绘制它们。如下右图所示，第 $3$ 行第 $2$ 列的砖块 $(3,2)$ 是灰色的，能被敲碎，使用一个叉代表其被敲碎了。
$\hspace{15pt}$对于使用蓝色斜线绘制的砖块，它们是一体的，牛可乐定义“蓝色极大连通块”为最大化上下左右（即四连通）连接的蓝色砖块个数、且不包含灰色砖块的连通块，例如，在上图中，唯一的“蓝色极大连通块”包含 $4$ 个蓝色砖块，分别为 $(3,3), (3,4), (4,3), (4,4)$。
$\hspace{15pt}$与真实生活一样，如果一个“蓝色极大连通块”的任意一个砖块都不与灰色砖块存在共边，则认为这个“蓝色极大连通块”完好地从原砖块掉落。例如，在上图中，要使得“蓝色极大连通块”掉落，至少需要敲碎八块砖块，如下图所示。
$\hspace{15pt}$特别地，对于位于边界上的“蓝色极大连通块”，不需要关注悬空的那些。例如，在下左图中，唯一的“蓝色极大连通块”包含 $2$ 个蓝色砖块，分别为 $(1,1), (1,2)$，其位于边界上，要使得它掉落，至少需要敲碎 $3$ 块砖块，如下图所示。
$\hspace{15pt}$现在，对于牛可乐给你的砖块矩阵，你需要帮助他分离出任意一块“蓝色极大连通块”，计算最少需要敲碎的灰色砖块个数。
$\hspace{15pt}$第一行输入两个正整数 $n, m \left(1 \leqq n, m \leqq 500\right)$ 代表砖块矩阵的行数和列数。
$\hspace{15pt}$接下来 $n$ 行，第 $i$ 行输入一个长度为 $m$ 、仅由字符 $\texttt{0'}$ 和 $\texttt{1’}$ 组成的字符串 $s_{i,1} s_{i,2} \cdots s_{i,m}$ ，其中 $s_{i,j}=\texttt{0'}$ 代表 $(i,j)$ 是灰色砖块，$s_{i,j}=\texttt{1’}$ 代表 $(i,j)$ 是蓝色斜线砖块。
$\hspace{15pt}$除此之外，保证至少存在一个“蓝色极大连通块”。
Output
$\hspace{15pt}$输出一个整数，代表最少需要敲碎的灰色砖块个数。
1
2
3
4
5
6
7
8
9
10
|
Input:
6 6
000000
000000
001100
001100
000000
000000
Output:
8
|
1
2
3
4
5
6
7
8
|
Input
4 5
10000
00111
11000
00000
Output
2
|
Solving
题目大意：给定数个由1字符组成的连通块，找出所有连通块中周边字符0最少的那个连通块，并输出其周边0的个数。
$\hspace{15pt}$由于数据量较小，我们可以先用DFS或者BFS将每个单独的连通块求出来，将他们的坐标存储到一个数据类型为pair(或者用结构体)的动态数组内。然后下一步遍历动态数组内所有元素，对其上下左右四个方向作搜索，若搜索到0，则这一个连通块的灰色砖块打破数+1,最后遍历所有的连通块，每次更新其打破数的最小值，即得到了答案。
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
|
#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 501;
const int M = 0;
int t;
char mp[N][N];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int n,m;
bool vis[N][N] = {false};//标记一定要用布尔数组！！而非直接将char值修改作为标记，否则会TLE！
int ans = INT_MAX;
vector<pii> block;//用于存储当前连通块里的所有方块坐标
bool check(int x,int y)
{
return x>0&&x<=n&&y>0&&y<=m;
}
//BFS染色各个连通块
void bfs(int x,int y)
{
queue<pii> q;
q.push({x,y});
vis[x][y] = true;
block.push_back({x,y});
while(!q.empty())
{
int curx = q.front().first;
int cury = q.front().second;
q.pop();
for(int i=0;i<4;i++)
{
int nx = curx + dx[i];
int ny = cury + dy[i];
if(check(nx,ny)&&mp[nx][ny]=='1'&&!vis[nx][ny])
{
q.push({nx,ny});
vis[nx][ny] = true;
block.push_back({nx,ny});
}
}
}
}
//返回每个连通块需要打破的灰砖块数
int update()
{
int temp = 0;
bool edge[N][N] = {false};//可能会重复选择，所以需要标记选过的灰砖
for(auto [x,y] : block)
{
for(int i=0;i<4;i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(check(nx,ny)&&mp[nx][ny]=='0'&&!edge[nx][ny])
{
edge[nx][ny] = true;
temp++;
}
}
}
return temp;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin >> n >> m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin >> mp[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j]=='1'&&!vis[i][j])
{
block.clear();
bfs(i,j);
int temp = update();
ans = min(ans,temp);
}
}
}
cout << ans << endl;
return 0;
}
|