CF377A Maze 解题报告_综合

CF377A Maze 解题报告

1 题目链接

http://codeforces.com/problemset/problem/377/A

2 题目整理

题目：迷宫

题目描述

帕维尔喜欢网格迷宫。网格迷宫是一个 n × m 矩形迷宫，其中每个单元格要么是空的，要么是一堵墙。仅当两个单元格都为空且具有共同的一面时，才能从一个单元格转到另一个单元格。

帕维尔画了一个网格迷宫，所有空单元格形成一个连接区域。也就是说，您可以从任何空单元格转到任何其他单元格。帕维尔不希望他的迷宫太小。他想把k个空单元格变成墙壁，这样所有剩余的单元格仍然可以形成一个连接的区域。

输入格式

第一行包含三个整数 n，m，k。

接下来的 n 行中的每一行都包含 m 个字符。他们描述了原始的迷宫。如果一行中的字符等于"."，则相应的单元格为空，如果字符等于"#"，则该单元格为墙。

输出格式

打印 n 行，每行包含 m 个字符：符合 Pavel 要求的新迷宫。将转换为墙壁的空单元格标记为"X"，其他单元格必须保持不变（即".“和”#"）。

保证存在解决方案。如果有多个解决方案，则可以输出其中任何一个。

样例输入1

3 4 2
#..#
..#.
#...

样例输出1

#.X#
X.#.
#...

样例输入2

5 4 5
#...
#.#.
.#..
...#
.#.#

样例输出2

#XXX
#X#.
X#..
...#
.#.#

数据范围

对于 $100\%$ 的数据:
$\le n, m \le 500$
$\le k \le s - 1$ (s为白色块个数)

3 题意分析

3.1 题目大意

给出一个单元格，请找到一种构造方式，使得在将k个空单元格改为墙壁之后，剩下的空单元格形成一个连通图。

3.2 样例分析

如上所述。

4 解法分析

不难发现，这道题要是考虑正推的话，需要考虑的情况繁多。那么，我们不妨用逆向思维来看看这道题，题目就变成选出s - k个格子，使他们构成连通图。此时，我们便可以使用搜索来解。设dfs(x,y)表示现在在(x,y)，那么每一次去寻找一个没有走过的点，直到大小为s - k即可。

AC代码

ACCode #001

// From Heart_Blue
// Rating 2425
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 5e2 + 10;
char chess[N][N];
int flag[N][N];
int n, m;
int c;
int dx[] = {
     0,0,-1,1 };
int dy[] = {
     -1,1,0,0 };
void dfs(int x, int y)
{
    if (x < 0 || x >= n) return;if (y < 0 || y >= m) return;if (c == 0) return;if (chess[x][y] == '#') return;if (flag[x][y]) return;flag[x][y] = 1;c--;for (int i = 0; i < 4; i++){
    dfs(x + dx[i], y + dy[i]);}}
int main()
{
    //freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);int k;int s = 0;cin >> n >> m >> k;int x, y;x = -1, y = -1;for (int i = 0; i < n; i++){
    for (int j = 0; j < m; j++){
    cin >> chess[i][j];if (chess[i][j] == '.') s++, x = i, y = j;}}c = s - k;MEM(flag, 0);dfs(x, y);for (int i = 0; i < n; i++){
    for (int j = 0; j < m; j++){
    if (chess[i][j] == '.'){
    if (flag[i][j]) putchar('.');else putchar('X');}else putchar('#');}putchar('\n');}return 0;
}

ACCode #002

// From ko_osaga
// Rating 3261
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;int n, m, s;
char str[555][555];
int dx[4] = {
    1, 0, -1, 0}, dy[4] = {
    0, 1, 0, -1};
bool vis[555][555];vector<pi> ord;void dfs(int x, int y){
    if(vis[x][y] || str[x][y] == '#') return;vis[x][y] = 1;ord.push_back(pi(x, y));for(int i=0; i<4; i++){
    if(x + dx[i] < 0 || x + dx[i] >= n || y + dy[i] < 0 || y + dy[i] >= m) continue;dfs(x + dx[i], y + dy[i]);}
}int main(){
    cin >> n >> m >> s;for(int i=0; i<n; i++) cin >> str[i];for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
    if(str[i][j] == '.'){
    dfs(i, j);reverse(ord.begin(), ord.end());for(int k=0; k<s; k++){
    str[ord[k].first][ord[k].second] = 'X';}for(int i=0; i<n; i++) cout << str[i] << endl;return 0;}}}
}

ACCode #003

// From 500kg
// Rating 2003
#include<cstdio>char a[1000][1000];
bool v[1000][1000];
int n, m, k;void f(int x, int y)
{
    if (x < 0 || x >= n || y < 0 || y >= m || a[x][y] != '.' || v[x][y])return;v[x][y] = true;f(x + 1, y);f(x - 1, y);f(x, y + 1);f(x, y - 1);if (k){
    a[x][y] = 'X';k--;}
}int main()
{
    int i, j;scanf("%d%d%d", &n, &m, &k);for (i = 0; i < n; i++)scanf("%s", a[i]);for (i = 0; i < n; i++){
    for (j = 0; j < m; j++)if (a[i][j] == '.')break;if (j < m)break;}f(i, j);for (i = 0; i < n; i++)puts(a[i]);
}