原来是想在填X的时候一边判断 ’.‘ 区域的连通性，发现很麻烦，说不定还超时。
另一种思路是，求出’.‘的数量是cou，需要填k个’X‘，则只需要找到一个有cou-k 个’.‘的连通域就可以了，剩下的k个’.‘全换成’X ‘
【CodeForces 377A】
#include
#include
#include int n, m, k;
char mapp[510][510];
int vis[510][510];
int sizev = sizeof(vis);
int cou, cc;
int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
///四个方向bool check(int x, int y) {
if (x >= n || x < 0 || y >= m || y < 0 || vis[x][y]) return false;
///越界和标记判断
return true;
}void dfs(int x, int y)
{
if (cc == k) return ;
///达到要求int i;
for (i = 0;
i < 4;
i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (!check(nx, ny)) continue;
vis[nx][ny] = 1;
mapp[nx][ny] = 'z';
///标记图中的‘.’
cc++;
dfs(nx, ny);
if (cc == k) return ;
///达到连同域中‘.’的数量要求，不用再找了
}}int main()
{
int i, j;
int s_x, s_y;
while (~scanf("%d%d%d", &n, &m, &k)) {
memset(vis, 0, sizev);
cou = 0;
cc = 0;
for (i = 0;
i < n;
i++) {scanf("%s", mapp[i]);
for (j = 0;
j < m;
j++) {
if (mapp[i][j] == '.') {
cou++;
s_x = i;
///记录最后一个‘.’的位置，以此为基准求连通域
s_y = j;
}if (mapp[i][j] == '#') vis[i][j] = 1;
///墙不能走}
}k = cou - k;
///关键，转换的一步cc++;
mapp[s_x][s_y] = 'z';
vis[s_x][s_y] = 1;
dfs(s_x, s_y);
for (i = 0;
i < n;
i++) {
for (j = 0;
j < m;
j++) {
if (mapp[i][j] == 'z')
putchar('.');
else if (mapp[i][j] == '.')
putchar('X');
else
printf("%c", mapp[i][j]);
}
puts("");
}
}
return 0;
}
推荐阅读
- 遇见蓝桥遇见你|小唐开始刷蓝桥（一）2020年第十一届C/C++ B组第二场蓝桥杯省赛真题
- DFS|使用DFS（深搜）遍历所有的序列所有的子组合（子序列）（排列组合中的组合）
- Pavel loves grid mazes（CodeForce 377A）
- DFS|CodeForces - 275B （广搜）
- 搜索|Wannafly模拟赛3-B 贝伦卡斯泰露（DFS）
- DFS|CodeForces - 1099D（树上贪心+DFS）
- Codeforces Round #336 (Div. 1) D. Power Tree
- BFS|Solve The Maze（codeforces）
- online|Codeforces #245 (Div. 2)C. Xor-tree（DFS&&贪心