撰写
- https://vjudge.net/contest/304586#problem/K
Pavel 喜欢网格迷宫。一个网格迷宫是一个 n × m 的长方形迷宫，其中每个单元格要么是空白的，要么是墙体。您可以从一个单元格走到另一个单元格，只要两个单元格均是空白的，且拥有一条公共的边。
Pavel 绘制了一个网格迷宫，包含的全部空白单元格形成了一个连通区域。换言之，您可以从任何一个空白的单元格，走到其它任意的空白单元格。Pavel 的迷宫如果墙体太少，他就不喜欢这个迷宫。他希望将 k 个空白的单元格转换为墙体，使得剩余的全部单元格仍然能够形成一个连通区域。请帮助他实现这个任务。
输入
第一行包含了三个整数 n, m, k (1 ≤ n, m ≤ 500, 0 ≤ k < s)，其中 n 和 m 分别是迷宫的高度和宽度，k 是 Pavel 希望加入的墙体数目，并且字母 s 表示原始迷宫中的空白单元格数目。
接下来的 n 行中，每行包含 m 个字符。它们描述了原始的迷宫。如果某行中的一个字符等于 “.“，则相应的单元格为空白；如果字符等于 “#“，则单元格为墙体。
输出
打印 n 行，每行包含 m 个字符：符合 Pavel 需求的新迷宫。将已转换为墙体的原始空白单元格标识为 “X“；其它单元格必须保留为未更改状态 (也就是 “.” 和 “#“)。
数据保证：存在一个解决方案。如果有多个解决方案，可输出它们中的任意一个。
示例
输入
3 4 2 #..# ..#. #...
输出
#.X# X.#. #...
输入
5 4 5 #... #.#. .#.. ...# .#.#
输出
#XXX #X#. X#.. ...# .#.#
- 题意
- 给一个迷宫，迷宫中有唯一的连通的块
- 去掉k个块中的点使其仍然连通，输出结果
- 题解
- 一开始我想用拓扑排序，用入度最少的作为拓扑入度为0的替代
- 但是图太大，一锅炖不下
- 逆向思维：去掉k个点，相当于保留cnt-k个点
- 那么我们只要bfs一次，标记并输出即可
- 用dfs也可以，直接将计数设置为全局变量即可
- 但是能用bfs，就不用dfs，因为回溯的退出条件比较难控制（不过这题因为用全局变量所以没啥问题）
- 代码
-
#include<algorithm> #include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <cassert> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define P(a,b,c) make_pair(a,make_pair(b,c)) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--) #define CLR(vis) memset(vis,0,sizeof(vis)) #define MST(vis,pos) memset(vis,pos,sizeof(vis)) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef pair<int,pair<int,int> >pii; typedef long long ll; typedef unsigned long long ull; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } template<class T>inline void gmax(T &A, T B) { (A<B)&&(A=B);//if(B>A)A=B; } template<class T>inline void gmin(T &A, T B) { (A>B)&&(A=B);//if(B<A)A=B; } template <class T> inline bool scan_d(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; //EOF while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(ll x) { if(x>9) outt(x/10); putchar(x%10+'0'); } char ma[505][505]; int vis[505][505]; pair<int,int>id; struct ss{ int x; int y; ss(int _x=0,int _y=0):x(_x),y(_y){} }; int n,m,k; int cnt=0; bool ok(int x,int y){ if(x>0&&x<=n&&y>0&&y<=m&&ma[x][y]=='.'){ return true; } return false; } int d[4][2]={-1,0,1,0,0,-1,0,1}; void bfs(){ queue<ss>q; while(!q.empty())q.pop(); q.push(ss(id.first,id.second)); vis[id.first][id.second]=1; ++cnt; if(cnt==k)return; while(!q.empty()){ ss tmp=q.front(); q.pop(); int x=tmp.x,y=tmp.y; rep(i,0,3){ int xx=x+d[i][0],yy=y+d[i][1]; if(ok(xx,yy)&&!vis[xx][yy]){ vis[xx][yy]=1; ++cnt; if(cnt==k)return; q.push(ss(xx,yy)); } } } } int main() { cin>>n>>m>>k; int cnt=0; rep(i,1,n) { scanf("%s", ma[i]+1); rep(j,1,m){ if(ma[i][j]=='.')id.first=i,id.second=j,++cnt; } } k=cnt-k; bfs(); rep(i,1,n){ rep(j,1,m){ if(vis[i][j]!=1&&ma[i][j]=='.'){ cout<<"X"; }else{ cout<<ma[i][j]; } } cout<<endl; } return 0; }
-