Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <ctime>
- #include <cstring>
- #include <string>
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <queue>
- using namespace std;
- #ifdef KVARK
- #define dbg(x) cout << #x << " = " << (x) << endl
- #define dbg2(x, y) cout << #x << " = " << (x) << "; " << #y << " = " << y << endl
- #else
- #define dbg(x) (void(1))
- #define dbg2(x, y) (void(1))
- #endif
- typedef long long llint;
- typedef vector<int> vi;
- typedef pair<int, int> pii;
- #define ALL(v) ((v).begin()), ((v).end())
- void task();
- int main() {
- #ifdef KVARK
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- #endif
- task();
- }
- const int N = 3e5 + 10;
- struct DSU {
- vi a;
- DSU() {
- a.resize(100 * 100 + 10000);
- for (int i = 0; i < a.size(); ++i)
- a[i] = i;
- }
- int get(int i) {
- if (a[i] == i)
- return i;
- return a[i] = get(a[i]);
- }
- void link(int f, int s) {
- f = get(f);
- s = get(s);
- a[f] = s;
- }
- int get(int i, int j) {
- return get(i * 100 + j);
- }
- void link(int i1, int j1, int i2, int j2) {
- link(i1 * 100 + j1, i2 * 100 + j2);
- }
- } dsu;
- int n, m;
- string grid[100];
- int used[100][100];
- int di[4] = { 0, 0, 1, -1 };
- int dj[4] = { -1, 1, 0, 0 };
- int isOk(int i, int j) {
- return i >= 0 && i < n && j >= 0 && j < m;
- }
- void bfs1() {
- memset(used, 0, sizeof(used));
- queue<pii> q;
- int ok = 0;
- for (int i = 0; i < n && !ok; ++i)
- for (int j = 0; j < m; ++j)
- if (grid[i][j] == '.') {
- q.push(pii{ i, j });
- used[i][j] = 1;
- ok = 1;
- break;
- }
- while (!q.empty()) {
- int i = q.front().first;
- int j = q.front().second;
- q.pop();
- for (int h = 0; h < 4; ++h) {
- int ii = i + di[h];
- int jj = j + dj[h];
- if (isOk(ii, jj) && grid[ii][jj] != '#' && !used[ii][jj]) {
- used[ii][jj] = 1;
- q.push(pii{ ii, jj });
- }
- }
- }
- }
- int used2[51][51];
- int bfs2(int I, int J) {
- memset(used2, 0, sizeof(used2));
- queue<pii> q;
- int ok = 0;
- for (int i = 0; i < n && !ok; ++i)
- for (int j = 0; j < m; ++j)
- if (grid[i][j] == '.') {
- q.push(pii{ i, j });
- used2[i][j] = 1;
- ok = 1;
- break;
- }
- while (!q.empty()) {
- int i = q.front().first;
- int j = q.front().second;
- q.pop();
- for (int h = 0; h < 4; ++h) {
- int ii = i + di[h];
- int jj = j + dj[h];
- if (isOk(ii, jj) && grid[ii][jj] != '#' && !used2[ii][jj]) {
- if (ii == I && jj == J) {
- continue;
- }
- used2[ii][jj] = 1;
- q.push(pii{ ii, jj });
- }
- }
- }
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < m; ++j)
- if (used2[i][j] == 0 && grid[i][j] == '.') {
- return 0;
- }
- return 1;
- }
- void task() {
- cin >> n >> m;
- for (int i = 0; i < n; ++i)
- cin >> grid[i];
- bfs1();
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < m; ++j)
- if (used[i][j] == 0 && grid[i][j] == '.') {
- printf("Impossible");
- return;
- }
- int c = 0;
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < m; ++j)
- if (grid[i][j] == '?' && used[i][j]) {
- c += bfs2(i, j);
- if (c) {
- printf("Ambiguous");
- exit(0);
- }
- }
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j)
- if (grid[i][j] == '?')
- printf("%c", used[i][j] ? '.' : '#');
- else
- printf("%c", grid[i][j]);
- printf("\n");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement