BFS Codeforces Round #297 (Div. 2) D. Arthur and Walls

题目传送门

 /*
题意:问最少替换'*'为'.',使得'.'连通的都是矩形
BFS:搜索想法很奇妙,先把'.'的入队,然后对于每个'.'八个方向寻找
在2*2的方格里,若只有一个是'*',那么它一定要被替换掉
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std; const int MAXN = 2e3 + ;
const int INF = 0x3f3f3f3f;
int n, m;
int dx[][] = {{,,},{,-,-},{-,-,},{,,}};
int dy[][] = {{,,},{,,},{,-,-},{,-,-}};
char s[MAXN][MAXN]; bool ok(int x, int y)
{
if (x < || x >= n) return false;
if (y < || y >= m) return false; return true;
} void BFS(void)
{
queue<pair<int, int> > Q;
for (int i=; i<n; ++i)
{
for (int j=; j<m; ++j)
{
if (s[i][j] == '.')
{
Q.push (make_pair (i, j));
}
}
} while (!Q.empty ())
{
int x = Q.front ().first; int y = Q.front ().second;
Q.pop ();
for (int i=; i<; ++i)
{
int cnt = ; int px, py; bool flag = true;
for (int j=; j<; ++j)
{
int tx = x + dx[i][j]; int ty = y + dy[i][j];
if (ok (tx, ty))
{
if (s[tx][ty] == '*')
{
cnt++; px = tx; py = ty;
}
}
else flag = false;
}
if (flag && cnt == )
{
s[px][py] = '.'; Q.push (make_pair (px, py));
}
}
}
} int main(void) //Codeforces Round #297 (Div. 2) D. Arthur and Walls
{
while (scanf ("%d%d", &n, &m) == )
{
for (int i=; i<n; ++i) scanf ("%s", s[i]);
BFS ();
for (int i=; i<n; ++i) printf ("%s\n", s[i]);
} return ;
} /*
5 5
.*.*.
*****
.*.*.
*****
.*.*.
6 7
***.*.*
..*.*.*
*.*.*.*
*.*.*.*
..*...*
*******
*/
上一篇:Codeforces Round #297 (Div. 2)D. Arthur and Walls 暴力搜索


下一篇:《时间序列分析及应用:R语言》读书笔记--第二章 基本概念