Advertisement
Guest User

Untitled

a guest
May 4th, 2016
378
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.28 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <ctime>
  4.  
  5. #include <cstring>
  6. #include <string>
  7. #include <iostream>
  8. #include <vector>
  9. #include <algorithm>
  10. #include <queue>
  11.  
  12. using namespace std;
  13.  
  14. #ifdef KVARK
  15. #define dbg(x) cout << #x << " = " << (x) << endl
  16. #define dbg2(x, y) cout << #x << " = " << (x) << "; " << #y << " = " << y << endl
  17. #else
  18. #define dbg(x) (void(1))
  19. #define dbg2(x, y) (void(1))
  20. #endif
  21.  
  22. typedef long long llint;
  23. typedef vector<int> vi;
  24. typedef pair<int, int> pii;
  25. #define ALL(v) ((v).begin()), ((v).end())
  26.  
  27. void task();
  28.  
  29. int main() {
  30. #ifdef KVARK
  31.     freopen("input.txt", "r", stdin);
  32.     freopen("output.txt", "w", stdout);
  33. #else
  34. #endif
  35.     task();
  36. }
  37.  
  38. const int N = 3e5 + 10;
  39.  
  40. struct DSU {
  41.     vi a;
  42.     DSU() {
  43.         a.resize(100 * 100 + 10000);
  44.         for (int i = 0; i < a.size(); ++i)
  45.             a[i] = i;
  46.     }
  47.  
  48.     int get(int i) {
  49.         if (a[i] == i)
  50.             return i;
  51.         return a[i] = get(a[i]);
  52.     }
  53.  
  54.     void link(int f, int s) {
  55.         f = get(f);
  56.         s = get(s);
  57.         a[f] = s;
  58.     }
  59.  
  60.     int get(int i, int j) {
  61.         return get(i * 100 + j);
  62.     }
  63.  
  64.     void link(int i1, int j1, int i2, int j2) {
  65.         link(i1 * 100 + j1, i2 * 100 + j2);
  66.     }
  67. } dsu;
  68.  
  69. int n, m;
  70. string grid[100];
  71. int used[100][100];
  72. int di[4] = { 0, 0, 1, -1 };
  73. int dj[4] = { -1, 1, 0, 0 };
  74.  
  75. int isOk(int i, int j) {
  76.     return i >= 0 && i < n && j >= 0 && j < m;
  77. }
  78.  
  79. void bfs1() {
  80.     memset(used, 0, sizeof(used));
  81.     queue<pii> q;
  82.     int ok = 0;
  83.     for (int i = 0; i < n && !ok; ++i)
  84.         for (int j = 0; j < m; ++j)
  85.             if (grid[i][j] == '.') {
  86.                 q.push(pii{ i, j });
  87.                 used[i][j] = 1;
  88.                 ok = 1;
  89.                 break;
  90.             }
  91.     while (!q.empty()) {
  92.         int i = q.front().first;
  93.         int j = q.front().second;
  94.         q.pop();
  95.         for (int h = 0; h < 4; ++h) {
  96.             int ii = i + di[h];
  97.             int jj = j + dj[h];
  98.             if (isOk(ii, jj) && grid[ii][jj] != '#' && !used[ii][jj]) {
  99.                 used[ii][jj] = 1;
  100.                 q.push(pii{ ii, jj });
  101.             }
  102.         }
  103.     }
  104. }
  105.  
  106. int used2[51][51];
  107. int bfs2(int I, int J) {
  108.     memset(used2, 0, sizeof(used2));
  109.     queue<pii> q;
  110.     int ok = 0;
  111.     for (int i = 0; i < n && !ok; ++i)
  112.         for (int j = 0; j < m; ++j)
  113.             if (grid[i][j] == '.') {
  114.                 q.push(pii{ i, j });
  115.                 used2[i][j] = 1;
  116.                 ok = 1;
  117.                 break;
  118.             }
  119.     while (!q.empty()) {
  120.         int i = q.front().first;
  121.         int j = q.front().second;
  122.         q.pop();
  123.         for (int h = 0; h < 4; ++h) {
  124.             int ii = i + di[h];
  125.             int jj = j + dj[h];
  126.             if (isOk(ii, jj) && grid[ii][jj] != '#' && !used2[ii][jj]) {
  127.                 if (ii == I && jj == J) {
  128.                     continue;
  129.                 }
  130.                 used2[ii][jj] = 1;
  131.                 q.push(pii{ ii, jj });
  132.             }
  133.         }
  134.     }
  135.     for (int i = 0; i < n; ++i)
  136.         for (int j = 0; j < m; ++j)
  137.             if (used2[i][j] == 0 && grid[i][j] == '.') {
  138.                 return 0;
  139.             }
  140.     return 1;
  141. }
  142.  
  143. void task() {
  144.     cin >> n >> m;
  145.     for (int i = 0; i < n; ++i)
  146.         cin >> grid[i];
  147.     bfs1();
  148.     for (int i = 0; i < n; ++i)
  149.         for (int j = 0; j < m; ++j)
  150.             if (used[i][j] == 0 && grid[i][j] == '.') {
  151.                 printf("Impossible");
  152.                 return;
  153.             }
  154.     int c = 0;
  155.     for (int i = 0; i < n; ++i)
  156.         for (int j = 0; j < m; ++j)
  157.             if (grid[i][j] == '?' && used[i][j]) {
  158.                 c += bfs2(i, j);
  159.                 if (c) {
  160.                     printf("Ambiguous");
  161.                     exit(0);
  162.                 }
  163.             }
  164.     for (int i = 0; i < n; ++i) {
  165.         for (int j = 0; j < m; ++j)
  166.             if (grid[i][j] == '?')
  167.                 printf("%c", used[i][j] ? '.' : '#');
  168.             else
  169.                 printf("%c", grid[i][j]);
  170.         printf("\n");
  171.     }
  172. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement