Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cassert>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- using namespace std;
- const int MAX_N = 505;
- char map[MAX_N][MAX_N];
- char ansMap[MAX_N][MAX_N];
- const int NO_VAL = -1;
- int rowPos[MAX_N], colPos[MAX_N];
- vector<int> g[MAX_N * MAX_N * 3];
- vector<int> revG[MAX_N * MAX_N * 3];
- int n;
- const int VERT = 0;
- const int HOR = 1;
- int encode(int i, int j, int ori) {
- assert(ori == VERT || ori == HOR);
- assert(i < n && j < n && i >= 0 && j >= 0);
- int ans = i * n + j;
- if (ori == HOR) {
- ans += n * n;
- }
- return ans;
- }
- int sign(int val) {
- if (val > 0) {
- return 1;
- } else if (val < 0) {
- return -1;
- } else {
- return 0;
- }
- }
- bool used[3 * MAX_N * MAX_N];
- vector<int> order;
- void topSort(int v) {
- used[v] = true;
- for (int u : g[v]) {
- if (!used[u]) {
- topSort(u);
- }
- }
- order.push_back(v);
- }
- int color[3 * MAX_N * MAX_N];
- int curC = 1;
- void colorDfs(int v) {
- color[v] = curC;
- for (int u : revG[v]) {
- if (color[u] == 0) {
- colorDfs(u);
- }
- }
- }
- int main() {
- #ifdef LOCAL
- freopen("C.in", "r", stdin);
- #endif
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- cin >> n;
- memset(rowPos, NO_VAL, sizeof rowPos);
- memset(colPos, NO_VAL, sizeof colPos);
- for (int i = 0; i < n; i++) {
- string s;
- cin >> s;
- for (int j = 0; j < n; j++) {
- map[i][j] = s[j];
- }
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- if (map[i][j] == 'O') {
- rowPos[i] = j;
- }
- }
- }
- for (int j = 0; j < n; j++) {
- for (int i = 0; i < n; i++) {
- if (map[i][j] == 'O') {
- colPos[j] = i;
- }
- }
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- if (map[i][j] != '+') {
- continue;
- }
- if (rowPos[i] == NO_VAL) {
- g[encode(i, j, HOR)].push_back(encode(i, j, VERT));
- } else {
- int dJ = sign(rowPos[i] - j);
- assert(dJ != 0);
- if (map[i][j + dJ] == '+') {
- g[encode(i, j, HOR)].push_back(encode(i, j + dJ, HOR));
- g[encode(i, j + dJ, VERT)].push_back(encode(i, j, VERT));
- } else if (map[i][j + dJ] == '.') {
- g[encode(i, j, HOR)].push_back(encode(i, j, VERT));
- } else {
- assert(map[i][j + dJ] == 'O');
- }
- }
- }
- }
- for (int j = 0; j < n; j++) {
- for (int i = 0; i < n; i++) {
- if (map[i][j] != '+') {
- continue;
- }
- if (colPos[j] == NO_VAL) {
- g[encode(i, j, VERT)].push_back(encode(i, j, HOR));
- } else {
- int dI = sign(colPos[j] - i);
- assert(dI != 0);
- if (map[i + dI][j] == '+') {
- g[encode(i, j, VERT)].push_back(encode(i + dI, j, VERT));
- g[encode(i + dI, j, HOR)].push_back(encode(i, j, HOR));
- } else if (map[i + dI][j] == '.') {
- g[encode(i, j, VERT)].push_back(encode(i, j, HOR));
- } else {
- assert(map[i + dI][j] == 'O');
- }
- }
- }
- }
- for (int i = 0; i < n * n * 2; i++) {
- if (!used[i]) {
- topSort(i);
- }
- }
- reverse(order.begin(), order.end());
- for (int a = 0; a < 3 * MAX_N * MAX_N; a++) {
- for (int b : g[a]) {
- revG[b].push_back(a);
- }
- }
- for (int v : order) {
- if (color[v] == 0) {
- curC++;
- colorDfs(v);
- }
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- if (map[i][j] != '+') {
- ansMap[i][j] = map[i][j];
- } else {
- int v1 = encode(i, j, VERT);
- int v2 = encode(i, j, HOR);
- if (color[v1] == color[v2]) {
- cout << "No\n";
- return 0;
- }
- if (color[v1] > color[v2]) {
- ansMap[i][j] = '|';
- } else {
- ansMap[i][j] = '-';
- }
- }
- }
- }
- cout << "Yes\n";
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- cout << ansMap[i][j];
- }
- cout << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement