Advertisement
Guest User

Untitled

a guest
Jan 26th, 2020
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <cassert>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. const int MAX_N = 505;
  10. char map[MAX_N][MAX_N];
  11. char ansMap[MAX_N][MAX_N];
  12. const int NO_VAL = -1;
  13.  
  14. int rowPos[MAX_N], colPos[MAX_N];
  15. vector<int> g[MAX_N * MAX_N * 3];
  16. vector<int> revG[MAX_N * MAX_N * 3];
  17. int n;
  18.  
  19. const int VERT = 0;
  20. const int HOR = 1;
  21.  
  22. int encode(int i, int j, int ori) {
  23.     assert(ori == VERT || ori == HOR);
  24.     assert(i < n && j < n && i >= 0 && j >= 0);
  25.     int ans = i * n + j;
  26.     if (ori == HOR) {
  27.         ans += n * n;
  28.     }
  29.     return ans;
  30. }
  31.  
  32. int sign(int val) {
  33.     if (val > 0) {
  34.         return 1;
  35.     } else if (val < 0) {
  36.         return -1;
  37.     } else {
  38.         return 0;
  39.     }
  40. }
  41.  
  42. bool used[3 * MAX_N * MAX_N];
  43. vector<int> order;
  44.  
  45.  
  46. void topSort(int v) {
  47.     used[v] = true;
  48.     for (int u : g[v]) {
  49.         if (!used[u]) {
  50.             topSort(u);
  51.         }
  52.     }
  53.     order.push_back(v);
  54. }
  55.  
  56. int color[3 * MAX_N * MAX_N];
  57. int curC = 1;
  58.  
  59. void colorDfs(int v) {
  60.     color[v] = curC;
  61.     for (int u : revG[v]) {
  62.         if (color[u] == 0) {
  63.             colorDfs(u);
  64.         }
  65.     }
  66. }
  67.  
  68. int main() {
  69. #ifdef LOCAL
  70.     freopen("C.in", "r", stdin);
  71. #endif
  72.     ios::sync_with_stdio(false);
  73.     cin.tie(0);
  74.     cout.tie(0);
  75.     cin >> n;
  76.     memset(rowPos, NO_VAL, sizeof rowPos);
  77.     memset(colPos, NO_VAL, sizeof colPos);
  78.     for (int i = 0; i < n; i++) {
  79.         string s;
  80.         cin >> s;
  81.         for (int j = 0; j < n; j++) {
  82.             map[i][j] = s[j];
  83.         }
  84.     }
  85.     for (int i = 0; i < n; i++) {
  86.         for (int j = 0; j < n; j++) {
  87.             if (map[i][j] == 'O') {
  88.                 rowPos[i] = j;
  89.             }
  90.         }
  91.     }
  92.  
  93.     for (int j = 0; j < n; j++) {
  94.         for (int i = 0; i < n; i++) {
  95.             if (map[i][j] == 'O') {
  96.                 colPos[j] = i;
  97.             }
  98.         }
  99.     }
  100.     for (int i = 0; i < n; i++) {
  101.         for (int j = 0; j < n; j++) {
  102.             if (map[i][j] != '+') {
  103.                 continue;
  104.             }
  105.             if (rowPos[i] == NO_VAL) {
  106.                 g[encode(i, j, HOR)].push_back(encode(i, j, VERT));
  107.             } else {
  108.                 int dJ = sign(rowPos[i] - j);
  109.                 assert(dJ != 0);
  110.                 if (map[i][j + dJ] == '+') {
  111.                     g[encode(i, j, HOR)].push_back(encode(i, j + dJ, HOR));
  112.                     g[encode(i, j + dJ, VERT)].push_back(encode(i, j, VERT));
  113.                 } else if (map[i][j + dJ] == '.') {
  114.                     g[encode(i, j, HOR)].push_back(encode(i, j, VERT));
  115.                 } else {
  116.                     assert(map[i][j + dJ] == 'O');
  117.                 }
  118.             }
  119.         }
  120.     }
  121.     for (int j = 0; j < n; j++) {
  122.         for (int i = 0; i < n; i++) {
  123.             if (map[i][j] != '+') {
  124.                 continue;
  125.             }
  126.             if (colPos[j] == NO_VAL) {
  127.                 g[encode(i, j, VERT)].push_back(encode(i, j, HOR));
  128.             } else {
  129.                 int dI = sign(colPos[j] - i);
  130.                 assert(dI != 0);
  131.                 if (map[i + dI][j] == '+') {
  132.                     g[encode(i, j, VERT)].push_back(encode(i + dI, j, VERT));
  133.                     g[encode(i + dI, j, HOR)].push_back(encode(i, j, HOR));
  134.                 } else if (map[i + dI][j] == '.') {
  135.                     g[encode(i, j, VERT)].push_back(encode(i, j, HOR));
  136.                 } else {
  137.                     assert(map[i + dI][j] == 'O');
  138.                 }
  139.             }
  140.         }
  141.     }
  142.     for (int i = 0; i < n * n * 2; i++) {
  143.         if (!used[i]) {
  144.             topSort(i);
  145.         }
  146.     }
  147.     reverse(order.begin(), order.end());
  148.     for (int a = 0; a < 3 * MAX_N * MAX_N; a++) {
  149.         for (int b : g[a]) {
  150.             revG[b].push_back(a);
  151.         }
  152.     }
  153.     for (int v : order) {
  154.         if (color[v] == 0) {
  155.             curC++;
  156.             colorDfs(v);
  157.         }
  158.     }
  159.     for (int i = 0; i < n; i++) {
  160.         for (int j = 0; j < n; j++) {
  161.             if (map[i][j] != '+') {
  162.                 ansMap[i][j] = map[i][j];
  163.             } else {
  164.                 int v1 = encode(i, j, VERT);
  165.                 int v2 = encode(i, j, HOR);
  166.                 if (color[v1] == color[v2]) {
  167.                     cout << "No\n";
  168.                     return 0;
  169.                 }
  170.                 if (color[v1] > color[v2]) {
  171.                     ansMap[i][j] = '|';
  172.                 } else {
  173.                     ansMap[i][j] = '-';
  174.                 }
  175.             }
  176.         }
  177.     }
  178.     cout << "Yes\n";
  179.     for (int i = 0; i < n; i++) {
  180.         for (int j = 0; j < n; j++) {
  181.             cout << ansMap[i][j];
  182.         }
  183.         cout << "\n";
  184.     }
  185.  
  186.     return 0;
  187. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement