11606: 【原1606】Interesting Island

题目

题目描述

author: fangbohui 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1606

Description

在一个n*m二维网格图中，有以下三种地形：'#'代表湖泊；'.'代表陆地；'?'代表陆地与湖泊均有可能的未知地形。

求是否存在一种或多种在未知地形填充湖泊/陆地的方案，使得最后地上全部的陆地区域组成一个四联通的联通块（陆地四联通是指，在任意一个陆地格子出发，只是任意使用上下左右四个方向操作，可以访问到任何一块其他的陆地）。

无解输出“Impossible”，多解输出“Ambiguous”，唯一解则须输出一个n*m的网格图，使得之前的“?”均被填充为“#”或“.”，且陆地四联通。

Input Format

第一行两个整数n, m代表地形的行、列数。 后面一个n行m列的矩阵代表地形。

Output Format

如题意（不含引号）。

Sample Input 1

5 7
#######
#..#..#
#..?..#
#..#..#
#######

Sample Output 1

#######
#..#..#
#.....#
#..#..#
#######

Sample Input 2

5 7
#######
#...#.#
#.?.?.#
#.#...#
#######

Sample Output 2

Ambiguous

Sample Input 3

5 7
#######
#.#.#.#
#.#?#.#
#.#.#.#
#######

Sample Output 3

Impossible

Limits

• 对于30%的数据，n，m不超过2；
• 对于60%的数据，n，m不超过7；
• 对于80%的数据，n，m不超过15；
• 对于100%的数据，n，m不超过50.

BugenZhao's solution

//
// Created by BugenZhao on 2019/5/17.
//

//
// Created by BugenZhao on 2019/4/5.
//

#ifndef SBL_BQUEUE_H
#define SBL_BQUEUE_H


#include <iostream>

template<typename Item>
class BQueue {
    class Node {
    public:
        Item item;
        Node *next;

        explicit Node(const Item &item, Node *next = nullptr) : item(item), next(next) {}

        explicit Node(Node *next = nullptr) : next(next) {}

        virtual ~Node() = default;
    };

    int N;
    Node *first;
    Node *last;

public:
    BQueue() {
        N = 0;
        first = last = nullptr;
    }

    bool isEmpty() const {
        return N == 0;
    }

    int size() const {
        return N;
    }

    void enqueue(Item item) {
        if (N == 0) {
            first = new Node{item};
            last = first;
        } else {
            Node *tmp = last;
            last = new Node{item};
            tmp->next = last;
        }
        ++N;
    }

    Item dequeue() {
        Item item = first->item;
        Node *tmp = first;
        first = first->next;
        if (N == 1) last = nullptr;
        delete tmp;
        --N;
        return item;
    }

    Item getFirst() const {
        return first->item;
    }

    Item getLast() const {
        return last->item;
    }

    void clear() {
        Node *tmp;
        while (first != nullptr) {
            tmp = first;
            first = first->next;
            delete tmp;
        }
        N = 0;
        first = last = nullptr;
    }

    virtual ~BQueue() {
        Node *tmp;
        while (first != nullptr) {
            tmp = first;
            first = first->next;
            delete tmp;
        }
    }

private:
    class Iterator {
        Node *it;
        Node *first;
        Node *last;
    public:

        Iterator(Node *first, Node *last) :
                it(first), first(first), last(last) {}

        bool hasNext() const {
            return it != nullptr;
        }

        Item &next() {
            Node *p = it;
            it = it->next;
            return p->item;
        }

        const Item &next() const {
            Node *p = it;
            it = it->next;
            return p->item;
        }
    };

public:
    Iterator iterator() const {
        return Iterator(first, last);
    }
};


#endif //SBL_BQUEUE_H


#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;

class Point {
public:
    int x, y;

    Point(int x = 0, int y = 0) :
            x(x), y(y) {}
};

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int height[50][50];
int r, c;
BQueue<Point> q;
Point *toFill;
int toFillCount;
bool *status;
int landCount = 0;

int ansCount = 0;
int ans[50][50];

void doDfs(int x, int y, int &curCount, bool flag[50][50]) {
    flag[x][y] = true;
    ++curCount;
    for (int i = 0; i < 4; ++i) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx < 0 || xx >= r || yy < 0 || yy >= c
            || !height[xx][yy] || flag[xx][yy])
            continue;
        doDfs(xx, yy, curCount, flag);
    }
}

int dfs(int x0, int y0) {
    bool flag[50][50]{};
    int curCount = 0;
    doDfs(x0, y0, curCount, flag);
    return curCount;
}

void DFS(int cur) {
    if (ansCount >= 2) return;
    if (cur == toFillCount) {
        if (landCount == 0)
            return;
        int x0 = -1, y0 = -1;
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                if (x0 != -1) goto interesting;
                else if (height[i][j]) x0 = i, y0 = j;
            }
        }
        interesting:
        if (dfs(x0, y0) == landCount) {
            if (ansCount == 0) {
                for (int i = 0; i < r; ++i) {
                    for (int j = 0; j < c; ++j) {
                        ans[i][j] = height[i][j];
                    }
                }
            }
            ++ansCount;
        }
    } else {
        status[cur] = true;
        height[toFill[cur].x][toFill[cur].y] = 1;
        ++landCount;
        DFS(cur + 1);
        status[cur] = false;
        height[toFill[cur].x][toFill[cur].y] = 0;
        --landCount;
        DFS(cur + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> r >> c;
    int x0 = -1, y0 = -1;

    if (r * c <= 150) {
        char tmp;
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                cin >> tmp;
                switch (tmp) {
                    case '#':
                        height[i][j] = 0;
                        break;
                    case '?':
                        height[i][j] = 1;
                        q.enqueue(Point(i, j));
                        break;
                    case '.':
                        height[i][j] = 1;
                        ++landCount;
                        if (x0 == -1) x0 = i, y0 = j;
                        break;
                }
            }
        }

        toFillCount = q.size();
        toFill = new Point[toFillCount];
        status = new bool[toFillCount]{};
        int ii = 0;
        while (!q.isEmpty()) toFill[ii++] = q.dequeue();

        DFS(0);

        if (ansCount == 0)
            cout << "Impossible" << endl;
        else if (ansCount == 1) {
            for (int i = 0; i < r; ++i) {
                for (int j = 0; j < c; ++j) {
                    cout << (ans[i][j] ? '.' : '#');
                }
                cout << '\n';
            }
        } else
            cout << "Ambiguous" << endl;

        return 0;
    } else {
        char tmp;
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                cin >> tmp;
                switch (tmp) {
                    case '#':
                        height[i][j] = 0;
                        break;
                    case '?':
                        height[i][j] = 1;
                        ++landCount;
                        q.enqueue(Point(i, j));
                        break;
                    case '.':
                        height[i][j] = 1;
                        ++landCount;
                        if (x0 == -1) x0 = i, y0 = j;
                        break;
                }
            }
        }
        if (landCount == 0) {
            cout << "Impossible" << endl;
            return 0;
        }
        if (x0 == -1)
            x0 = q.getFirst().x, y0 = q.getLast().y;

        if (dfs(x0, y0) != landCount) {
            cout << "Impossible" << endl;
            return 0;
        } else {
            bool ambiguous = false;
            --landCount;
            while (!ambiguous && !q.isEmpty()) {
                Point point = q.dequeue();
                height[point.x][point.y] = 0;
                if (dfs(x0, y0) == landCount) ambiguous = true;
                height[point.x][point.y] = 1;
            }
            if (ambiguous) {
                cout << "Ambiguous" << endl;
            } else {
                for (int i = 0; i < r; ++i) {
                    for (int j = 0; j < c; ++j) {
                        cout << (height[i][j] ? '.' : '#');
                    }
                    cout << '\n';
                }
            }
        }
        return 0;
    }
}

FineArtz's solution

/* Interesting Island */
#include <iostream>
#include <cstring>
using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, m;
char a[55][55];
bool v[55][55], isol = true;

void floodfill(int x, int y){
    v[x][y] = true;
    for (int k = 0; k < 4; ++k){
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != '#' && !v[nx][ny])
            floodfill(nx, ny);
    }
}

void checkfill(int x, int y){
    if (a[x][y] == '.'){
        isol = false;
        return;
    }
    v[x][y] = true;
    for (int k = 0; k < 4; ++k){
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != '#' && !v[nx][ny])
            checkfill(nx, ny);
        if (!isol)
            return;
    }
}

void realfill(int x, int y){
    v[x][y] = true;
    a[x][y] = '#';
    for (int k = 0; k < 4; ++k){
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == '?' && !v[nx][ny])
            realfill(nx, ny);
    }
}

bool check(){
    bool flag = true;
    memset(v, 0, sizeof(v));
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            if (a[i][j] == '.'){
                floodfill(i, j);
                flag = false;
                break;
            }
        }
        if (!flag)
            break;
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            if (a[i][j] == '.' && !v[i][j])
                return false;
        }
    }
    return true;
}

void checkIso(int i, int j){
    isol = true;
    memset(v, 0, sizeof(v));
    checkfill(i, j);
    if (isol){
        memset(v, 0, sizeof(v));
        realfill(i, j);
    }
}

int main(){
    bool flag = false;
    int cnt = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            cin >> a[i][j];
            if (a[i][j] == '.')
                flag = true;
            if (a[i][j] == '?')
                ++cnt;
        }
    }
    if (!flag){
        if (cnt >= 2){
            cout << "Ambiguous" << endl;
            return 0;
        }
        else if (cnt == 0){
            cout << "Impossible" << endl;
            return 0;
        }
        else{
            for (int i = 1; i <= n; ++i){
                for (int j = 1; j <= m; ++j){
                    if (a[i][j] == '?')
                        cout << '.';
                    else
                        cout << a[i][j];
                }
                cout << endl;
            }
            return 0;
        }
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            if (a[i][j] == '?'){
                checkIso(i, j);
                if (a[i][j] != '?')
                    continue;
                bool flag1 = false, flag2 = false;
                a[i][j] = '.';
                flag1 = check();
                a[i][j] = '#';
                flag2 = check();
                if (flag1 && flag2){
                    cout << "Ambiguous" << endl;
                    return 0;
                }
                if (!flag1 && !flag2){
                    cout << "Impossible" << endl;
                    return 0;
                }
                a[i][j] = '.';
            }
        }
    }
    bool imp = true;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i][j] == '.'){
                imp = false;
                break;
            }
    if (imp){
        cout << "Impossible" << endl;
        return 0;
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j)
            cout << a[i][j];
        cout << endl;
    }
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
using namespace std;

char map_data[59][59] = { 0 };
bool visited[59][59] = { 0 };

int lx[2509] = { 0 }, ly[2509] = { 0 };

int dx[] = { 0,1,0,-1 },
dy[] = { 1,0,-1,0 };

int n, m;

int dfs(int start_x, int start_y) {
    visited[start_x][start_y] = true;
    int ans = 0;
    if (map_data[start_x][start_y] == '.')
        ++ans;
    for (int i = 0; i < 4; ++i) {
        auto next_x = start_x + dx[i],
            next_y = start_y + dy[i];
        if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m &&
            map_data[next_x][next_y] != '#' && !visited[next_x][next_y]) {
            ans += dfs(next_x, next_y);
        }
    }
    return ans;
}

int main() {
    int land_cnt = 0, l_cnt = 0;
    int start_x = 0, start_y = 0;

    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("\n");
        for (int j = 0; j < m; ++j) {
            scanf("%c", &map_data[i][j]);
            if (map_data[i][j] == '.') {
                if (land_cnt == 0) {
                    start_x = i;
                    start_y = j;
                }
                ++land_cnt;
            }
            else if (map_data[i][j] == '?') {
                lx[l_cnt] = i;
                ly[l_cnt] = j;
                ++l_cnt;
            }
        }
    }

    auto visited_land = dfs(start_x, start_y);
    if (visited_land < land_cnt) {
        printf("Impossible");
        return 0;
    }
    for (int i = 0; i < l_cnt; ++i) {
        //判断是否未访问到
        if (!visited[lx[i]][ly[i]]) {
            map_data[lx[i]][ly[i]] = '#';
        }
    }
    for (int i = 0; i < l_cnt; ++i) {
        if (!visited[lx[i]][ly[i]])
            continue;
        //修改
        map_data[lx[i]][ly[i]] = '#';
        memset(visited, 0, sizeof(visited));
        visited_land = dfs(start_x, start_y);
        if (visited_land == land_cnt) {
            printf("Ambiguous");
            return 0;
        }
        map_data[lx[i]][ly[i]] = '?';
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (map_data[i][j] == '?')
                printf(".");
            else
                printf("%c", map_data[i][j]);
        }
        printf("\n");
    }

    return 0;
}