# 11606: 【原1606】Interesting Island

### 题目描述

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

## 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;
}
``````