# CF 538 D. Weird Chess

:::info
[Link](https://codeforces.com/contest/538/problem/D)
:::

:::spoiler 目錄
[toc]
:::

## 題意

給定一個$n\times n$的棋盤，盤面上有至少一枚以上以小寫"$o$"表示的棋子和數個棋子可以移動過去的位置以小寫"$x$"代表，其他位置則以"$.$"表示。
請找出一個$(2n - 1) * (2n - 1)$的棋盤，一樣以$x$表示可移動位置，盤上只有唯一一枚在中心的棋子 $o$ ，棋盤上面所有的 $x$ 可以剛好符合前面給的棋盤的移動範圍。
同一棋盤可能會有多種對應的解，只要輸出其中一個即可
如假設給定以下棋盤：

oxxxx
x...x
x...x
x...x
xxxxo

則下面的棋盤為其中一種解：

....x....
....x....
....x....
....x....
xxxxoxxxx
....x....
....x....
....x....
....x....

## 官解

### 思路

思路基本上和初見解一樣，就不贅述了。

>> 不過題解說有$O{(n^2\log{n})}$的做法，不過它沒有提供實作方式，但底下有留言說可以用一維FFT做，但請原諒我太弱，沒辦法自己做出來QQ

### code

>> 仿照官解提供的作法寫的，老實說沒有比初見解好到哪裡去XD

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
 
using namespace std;
 
string board[55];
int ans[105][105];
 
void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> board[i];
    }
    
    const int len = 2 * n - 1, mid = n - 1;
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
        if (board[i][j] != 'o') continue;
        for (int x = 0; x < n; ++x) for (int y = 0; y < n; ++y) {
            if (board[x][y] != '.') continue;
            ans[x - i + mid][y - j + mid] = 1;
        }
    }
    
    for (int x = 0; x < n; ++x) for (int y = 0; y < n; ++y) {
        if (board[x][y] != 'x') continue;
        bool failed = true;
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
            if (board[i][j] != 'o') continue;
            failed &= ans[x - i + mid][y - j + mid];
        }
        if (failed) {
            cout << "NO\n";
            return;
        }
    }
    
    ans[mid][mid] = 2;
    cout << "YES\n";
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len; ++j) {
            cout << "x.o"[ans[i][j]];
        }
        cout << "\n";
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
}

## 初見解

### 思路

首先可以觀察到棋盤的大小$n\times n(n\le 50)$很小，所以可以嘗試暴力枚舉。

不過雖說暴力枚舉，也不能太過暴力。例如枚舉$(2n+1)\times (2n+1)$盤面中的所有可能，這樣最多要做$3^{(2n+1)\times (2n+1)}=3^{101^2}$，做得完才有鬼。
一個可能的思考方向是對於每個 $x$ ，枚舉他們屬於哪個 $o$ ，但評估這樣做法的時間複雜度，會發現 $x$ 和 $o$ 的量級都為$O{(n^2)}$，然後枚舉 $x$ 是否屬於當前的 $o$ 時，又要再枚舉所有的 $o$ 來驗證是否符合。所以時間複雜度為$O{(cnt(x)\times cnt(o)\times cnt(x)}=O{((n^2)\times (n^2)\times (n^2))}=O{(n^6)}$，套入這題的最大$n$，大約是$15625000000$，時間上會被卡掉。
這時可以"換個方向思考"，枚舉旗子不能移動到哪些位置，然後再驗證這樣的解是否能到達所有的 $x$ 。
這種做法的實作可以先假設棋子可以移動到任何地方，然後再枚舉所有的 $.$ 和 $o$ ，因為由 $o$ 指向 $.$ 的移動向量必定不能是 $x$ ，所以就可以排除它的可能性，將其換成 $.$ 。最後就可以得到一個保證不會踩到 $.$ 的解，不過這樣仍不能確定它能觸及所有 $x$ ，所以另外枚舉所有的 $o$ 和所有的 $x$ ，確認對於每個 $x$ ，至少存在一枚棋子 $o$ 能移動過來，如果這步驟通過則答案為"YES"；反之為"NO"。這樣的時間複雜度為$O{(n^4)}$

### code

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

#define F first
#define S second
#define SZ(x) (int)(x).size()

using namespace std;
using pii = pair<int, int>;

char board[55][55], ans[105][105];

void solve() {
    int n;
    cin >> n;
    vector<pii> chess, attacked;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> board[i][j];
            if (board[i][j] == 'o') chess.emplace_back(i, j);
            if (board[i][j] == 'x') attacked.emplace_back(i, j);
        }
    }
    
    const int len = 2 * n - 1, mid = len / 2;
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len; ++j) {
            ans[i][j] = 'x';
        }
    }
    ans[mid][mid] = 'o';
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] != '.') continue;
            for (int k = 0; k < SZ(chess); ++k) {
                pii d {mid + (i - chess[k].F), mid + (j - chess[k].S)};
                if (d.F >= 0 && d.F < len && d.S >= 0 && d.S < len) {
                    ans[d.F][d.S] = '.';
                }
            }
        }
    }
    
    for (int i = 0; i < SZ(attacked); ++i) {
        bool ok = false;
        for (int j = 0; j < SZ(chess); ++j) {
            if (ans[mid + attacked[i].F - chess[j].F][mid + attacked[i].S - chess[j].S] == 'x') ok = true;
        }
        if (!ok) {
            cout << "NO\n";
            return;
        }
    }
    
    cout << "YES\n";
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len; ++j) {
            cout << ans[i][j];
        }
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
}

###### tags: `每日CF梗題挑戰`