Codeforces Round #222 (Div. 2): C. Maze(BFS)
程序员文章站
2022-06-04 09:58:53
...
题意: 给你一个n*m的迷宫,'.'是路,'#'是墙,输入保证所有的'.'构成一个联通块,要求为这个迷宫再添加k面墙,使得剩下所有的'.'仍然构成一个联通块
思路:反过来处理,先将所有的'.'全部变成墙,然后从其中一个'.'开始广搜即可
#include<stdio.h>
#include<queue>
using namespace std;
typedef struct R
{
int x;
int y;
}Point;
Point now, temp;
queue<Point> q;
char str[555][555];
int vis[555][555], dir[4][2] = {1,0,0,1,-1,0,0,-1};
int main(void)
{
int n, m, k, i, j, sum;
scanf("%d%d%d", &n, &m, &k);
for(i=1;i<=n;i++)
scanf("%s", str[i]+1);
sum = 0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(str[i][j]=='.')
{
str[i][j] = 'X', sum++;
if(q.empty())
{
now.x = i, now.y = j;
q.push(now);
vis[i][j] = 1;
}
}
}
}
k = sum-k;
for(i=1;i<=k;i++)
{
now = q.front();
q.pop();
str[now.x][now.y] = '.';
for(j=0;j<=3;j++)
{
temp.x = now.x+dir[j][0];
temp.y = now.y+dir[j][1];
if(str[temp.x][temp.y]=='X' && vis[temp.x][temp.y]==0)
{
q.push(temp);
vis[temp.x][temp.y] = 1;
}
}
}
while(q.empty()==0)
q.pop();
for(i=1;i<=n;i++)
puts(str[i]+1);
return 0;
}
上一篇: 沙虾营养价值和功效,这篇文章告诉你
下一篇: 富含维c的水果具体有哪些呢,一起来看看吧
推荐阅读
-
Codeforces Round #320 (Div. 2) C. A Problem about Polyline ( 数学 )
-
Codeforces Round #654 (Div. 2)-C. A Cookie for You
-
Educational Codeforces Round 85 (Rated for Div. 2) C. Circle of Monsters(前缀和 预处理 贪心)
-
Codeforces Round #533 (Div. 2) D. Kilani and the Game(bfs+模拟)
-
Codeforces Round #651 (Div. 2) C. Number Game
-
Codeforces Round #668 (Div. 2)-C. Balanced Bitstring
-
Educational Codeforces Round 99 (Rated for Div. 2) C. Ping-pong
-
Codeforces Round #256 (Div. 2) C. Painting Fence(分治贪心)_html/css_WEB-ITnose
-
Codeforces Round #277 (Div. 2)-C. Palindrome Transformation (贪心)_html/css_WEB-ITnose
-
Codeforces Round #222 (Div. 2)