ATCODER ABC 450 C题解
<h1 id="atcoder-abc-450-c">ATCODER ABC 450 C</h1><p>(C - Puddles)</p>
<h2 id="题意概述">题意概述:</h2>
<p>二维字符数组中,找到联通的.的组合并且处在内部,没有点在最外层</p>
<h2 id="难点">难点:</h2>
<p>因为想不到或者不知道这道题的算法是什么,我想枚举模拟,但是在枚举模拟的过程中,我发现,我模拟从一个串的开始到串的末尾,这个过程很难模拟出来,所以暴力做法也写不出来,最后,看官方题解以及问ai,才知道这道题要用BFS(广度优先搜索)</p>
<h2 id="bfs">BFS:</h2>
<h3 id="为什么要用bfs">为什么要用BFS</h3>
<ol>
<li>这道题是一个连通块问题,等效于要求我们统计“不漏水”的水坑,<code>bfs</code>的核心思想就是从一个点开始,向四周扩散,所以这道题的要求很契合bfs</li>
</ol>
<h3 id="具体思路">具体思路</h3>
<ul>
<li>
<p>用两个数组表示平移到上下左右</p>
</li>
<li>
<p>用一个二维bool数组表示该格子是否被扫描过</p>
</li>
<li>
<p>循环每个字符</p>
<ul>
<li>
<p>假如一个字符没被扫描过,并且是<code>.</code>,以它为头建造一个队列(存储pair),记住存入队列就马上标记(原因见下文).</p>
</li>
<li>
<p>设定一个bool数来表示连通串是否有点在边界</p>
</li>
<li>
<p>bfs寻找:首先判断当前的坐标是否在边界内,即使在边界,还是要把邻居找完,不然之后还是循环到邻居还是要再找,可能导致重复找邻居,效率低下.找邻居(注意判断坐标边界条件,将邻居push进队列,进队列就标记)</p>
</li>
<li>
<p>进队列就标记的原因:</p>
<p>如下例子所示:</p>
<h3 id="1-22-地图的包抄过程">1. 2×2 地图的“包抄”过程</h3>
<p>假设四个点全是水坑 <code>.</code>：</p>
<ul>
<li><strong>A</strong> <span class="math inline">\((0,0)\)</span> —— 起点</li>
<li><strong>B</strong> <span class="math inline">\((1,0)\)</span> —— A 的下方邻居</li>
<li><strong>C</strong> <span class="math inline">\((0,1)\)</span> —— A 的右方邻居</li>
<li><strong>D</strong> <span class="math inline">\((1,1)\)</span> —— <strong>B 的右方邻居，同时也是 C 的下方邻居</strong></li>
</ul>
<ol>
<li><strong>第一步：处理 A <span class="math inline">\((0,0)\)</span></strong>
<ul>
<li>A 看向四周，发现了 B <span class="math inline">\((1,0)\)</span> 和 C <span class="math inline">\((0,1)\)</span>。</li>
<li>A 把 B 和 C 都丢进队列排队。</li>
<li><em>此时队列</em>：<code></code>。<strong>注意：此时 B 和 C 还没出队，所以还没被贴上 <code>cg=1</code> 的标签。</strong></li>
</ul>
</li>
<li><strong>第二步：轮到 B <span class="math inline">\((1,0)\)</span> 出队</strong>
<ul>
<li>B 贴上标签 <code>cg=1</code>。</li>
<li>B 看向它的邻居，发现了 <strong>D <span class="math inline">\((1,1)\)</span></strong>。</li>
<li>B 发现 D 还没贴标签，于是把 <strong>D 丢进队列</strong>。</li>
<li><em>此时队列</em>：<code></code>。<strong>注意：此时 D 已经在排队了，但因为还没出队，它的标签 <code>cg</code> 依然是 0。</strong></li>
</ul>
</li>
<li><strong>第三步：轮到 C <span class="math inline">\((0,1)\)</span> 出队</strong>
<ul>
<li>C 贴上标签 <code>cg=1</code>。</li>
<li>C 看向它的邻居，也发现了 <strong>D <span class="math inline">\((1,1)\)</span></strong>！</li>
<li><strong>关键冲突点</strong>：C 检查 <code>cg</code>，发现竟然是 <strong>0</strong>（因为 D 还在后面排队呢，没轮到它贴标签）。</li>
<li>C 以为 D 是个没人管的“新发现”，于是<strong>又把 D 丢进了一次队列</strong>。</li>
<li><em>最终队列</em>：<code></code>。</li>
</ul>
</li>
</ol>
<hr>
<h3 id="2-为什么这很可怕">2. 为什么这很可怕？</h3>
<p>虽然 <span class="math inline">\((1,0)\)</span> 和 <span class="math inline">\((0,1)\)</span> 互不相识，但它们像两个不沟通的部门，同时看中了同一个员工 <strong>D</strong>。</p>
<ul>
<li>在一个大迷宫里，任何一个空格子（比如 <span class="math inline">\((x, y)\)</span>）通常都有 4 个邻居。</li>
<li>这意味着，如果你不在<strong>入队那一刻</strong>就贴上标签，这个格子可能会被它的上下左右邻居<strong>每人举报一次</strong>。</li>
<li>在你的 <code>while</code> 循环里，原本这个格子只需要处理 1 次，现在却要处理 4 次。而这 4 次处理又会引发出更多的重复……这种冗余会像病毒一样在你的队列里疯狂繁殖。</li>
</ul>
</li>
<li>
<p>假如队列空后bool数不变,那么++count</p>
</li>
</ul>
</li>
</ul>
<h2 id="代码">代码:</h2>
<pre><code class="language-cpp">#include <bits/stdc++.h>
using i64 = long long;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void solve(){
int h, w;
std::cin >> h >> w;
std::vector<std::string> s(h);
for(int i = 0; i < h; ++i){
std::cin >> s;
}
std::vector<std::vector<bool>> cg(h,std::vector<bool> (w,0));
int count = 0;
for(int i = 0; i < h; ++i){
for(int j = 0; j < w; ++j){
if(s == '.' && cg == 0){
std::queue<std::pair<int, int>> q;
q.push({i,j});
cg = 1;
bool is = 1;
while(!q.empty()){
auto = q.front();
q.pop();
int nx, ny;
if(x == 0 || x == h - 1 || y == 0 || y == w - 1){
is = 0;
}
for(int k = 0 ; k < 4; ++k){
nx = x + dx;
ny = y + dy;
if(nx >= 0 && nx < h && ny >= 0 && ny < w){
if(s == '.' && cg == 0){
q.push({nx,ny});
cg = 1;
}
}
}
}
if(is == 1){
++count;
}
}
}
}
std::cout << count;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
solve();
return 0;
}
</code></pre><br><br>
来源：https://www.cnblogs.com/XZXZZX/p/19786727
頁:
[1]