这题其实比我想象中的好做…
不过我做题还是容易出问题,其实吃了一次罚时,没有一遍过。
1.首先,我们对图像进行预处理,从两个斑点中挑一个,将其选中为那个“泄洪的高坡”(flood fill)。
1.1.那么,怎么处理?很简单,对第一个’X’点做标记,然后,就对这个x点进行bfs扩散,把所有的x点标记成新的高坡区域‘0’。
注意:第一个点也要标记预先标记成‘0’。我一开始想着它最终一定会被其他的点标记为‘0’所以没管。但实际上,有且仅有一个’x’点不也是一种斑点吗?我吃wa就是错在这里。
2.接下来,bfs扩散,如果说1.1.的扩散是对x点作标记,那么我们现在就是对’.’点标记,这里是洪水区。当水碰到另外的斑点时就说明,它已经不能继续扩散了,bfs结束,因为我们是在第x次扩散被阻止的,所以实际距离是x-1。当然你大可以在main函数中就bfs(0);但是我觉得从1开始会更有利于理解。
#include <bits/stdc++.h>
#define var long long
#define val const long long
#define x first
#define y second
using namespace std;
typedef pair<var,var> PII;
val N = 110;
char li[N][N];
var n, m;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
deque<PII>hanging, st;
var len,output;
void bfs1()//涂色
{
while (st.size())
{
var a = st.front().x, b = st.front().y;
st.pop_front();
for (int i = 0; i < 4; i++)
{
int an = a + dx[i], bn = b + dy[i];
if (an && bn && li[an][bn] == 'X')
{
li[an][bn] = '0';
st.push_back({ an,bn });
hanging.push_back({ an,bn });
}
}
}
return;
}
void bfs2(int u)//洪水填充开始,u为层级
{
len = hanging.size();
for (int i = 0; i < len; i++)
{
var a = hanging.front().x, b = hanging.front().y;
hanging.pop_front();
for (int i = 0; i < 4; i++)
{
int an = a + dx[i], bn = b + dy[i];
if (an && bn&&an<=n&&bn<=m)
{
if (li[an][bn] == 'X')//碰x,一切结束
{
//cout << an << " " << bn << endl;
output = u-1;
return;
}
else if (li[an][bn] == '.')
{
li[an][bn] = u+'X';
hanging.push_back({ an,bn });
}
}
}
}
return bfs2(u + 1);
}
int main()
{
cin >> n >> m;
var fix = -1, fiy = -1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> li[i][j];
if (li[i][j] == 'X' && fix == -1)
{
fix = i, fiy = j;
li[i][j] = '0';
}
}
}
hanging.push_back({ fix,fiy });
st.push_back({ fix,fiy });
bfs1();
bfs2(1);
cout << output << endl;
}
另外,那个 li[an][bn] = u+’X’; 这一步只是便于debug的操作,实际上你可以随便做标记,之所以是’X’是放置ascii码在某一步滚到了X,导致错误结算