本文主要是介绍CodeForces 377A Maze（暴力），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：CodeForces 377A Maze
题目大意：给出一张图，将k个位置置为X，使得剩下的空位置仍能联通。
解题思路：暴力。因为题目肯定保证有答案，所以水了很多，但是它可能一开始就有不连通的块，所以先用BFS找出所有的联通块，然后按照面积从小到大排序，用DFS进行填充。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>using namespace std;const int N = 505;
const int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };int n, r, l, k, v[N][N];
char g[N][N];void init() {scanf("%d%d%d", &r, &l, &k);n = 0;memset(v, 0, sizeof(v));for (int i = 0; i < r; i++) scanf("%s", g[i]);
}void dfs(int x, int y) {for (int i = 0; i < 4; i++) {int a = x + dir[i][0], b = y + dir[i][1];if (a < 0 || a >= r || b < 0 || b >= l) continue;if (v[a][b] || g[a][b] == '#') continue;v[a][b] = 1; dfs(a, b);}if (k) {k--; v[x][y] = 2;}
}int main() {init();for (int i = 0; i < r; i++) {for (int j = 0; j < l; j++) if (v[i][j] == 0 && g[i][j] == '.') {dfs(i, j);}} for (int i = 0; i < r; i++) {for (int j = 0; j < l; j++) {if (v[i][j] == 2) printf("X");else printf("%c", g[i][j]);}printf("\n");}return 0;
}
这篇关于CodeForces 377A Maze（暴力）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
