QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#222683#6398. Puzzle: Tapatselmegkh#WA 1ms3556kbC++175.2kb2023-10-21 17:58:022023-10-21 17:58:03

Judging History

你现在查看的是最新测评结果

  • [2023-10-21 17:58:03]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3556kb
  • [2023-10-21 17:58:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
int n, m;
char a[100][100];
int b[100][100];
bool inside(int x, int y, int x1, int y1, int x2, int y2) {
    return x1 <= x && x <= x2 && y1 <= y && y <= y2;
}
bool ok(int x, int y) {
    return x >= 0 && x < 2 * n - 1 && y >= 0 && y < 2 * m - 1;
}
bool check(int x, int y) {
    return x >= 0 && x < 2 * n - 1 && y >= 0 && y < 2 * m - 1 && a[x][y] == '#';
}
bool check(pair<int, int> p) {
    return check(p.first, p.second);
}
int count(int x, int y) {
    int ans = 0;
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            if (check(x + i, y + j)) {
                ans++;
            }
        }
    }
    return ans;
}
bool color(int x, int y) {
    if (ok(x, y) && a[x][y] == '.') {
        a[x][y] = '#';
        return 1;
    }
    return 0;
}
bool color(pair<int, int> p) {
    return color(p.first, p.second);
}
bool rec(int x1, int y1, int x2, int y2) {
    if (x1 > x2 || y1 > y2) {
        return 1;
    }
    if (x1 < x2 && y1 < y2) {
        for (int i = y1 + 1; i <= y2 - 1; i++) {
            a[x1 + 1][i] = a[x2 - 1][i] = '#';
        }
        for (int i = x1 + 1; i <= x2 - 1; i++) {
            a[i][y1 + 1] = a[i][y2 - 1] = '#';
        }
        if (!rec(x1 + 2, y1 + 2, x2 - 2, y2 - 2)) {
            return 0;
        }
    }
    vector<pair<int, int>> M, L, R;
    if (x1 == x2 && y1 == y2) {
        M.eb(x1, y1);
        L.eb(-1, -1);
        R.eb(-1, -1);
    } else if (x1 == x2) {
        M.eb(x1, y1);
        L.eb(-1, -1);
        R.eb(x1, y1 + 1);
        for (int i = y1 + 2; i < y2; i += 2) {
            M.eb(x1, i);
            L.eb(x1, i - 1);
            R.eb(x1, i + 1);
        }
        M.eb(x1, y2);
        L.eb(x1, y2 - 1);
        R.eb(-1, -1);
    } else if (y1 == y2) {
        M.eb(x1, y1);
        L.eb(-1, -1);
        R.eb(x1 + 1, y1);
        for (int i = x2 + 2; i < x2; i += 2) {
            M.eb(i, y1);
            L.eb(i - 1, y1);
            R.eb(i + 1, y1);
        }
        M.eb(x2, y1);
        L.eb(x2 - 1, y1);
        R.eb(-1, -1);
    } else {
        for (int i = y1; i < y2; i += 2) {
            if (M.empty() || M.back() != pair{x1, i}) {
                M.eb(x1, i);
                i == y1 ? (x1 == x2 ? L.eb(-1, -1) : L.eb(x1 + 1, i)) : L.eb(x1, i - 1);
                i == y2 ? (x1 == x2 ? R.eb(-1, -1) : R.eb(x1 + 1, i)) : R.eb(x1, i + 1);
            }
        }
        for (int i = x1; i < x2; i += 2) {
            if (M.empty() || M.back() != pair{i, y2}) {
                M.eb(i, y2);
                i == x1 ? (y1 == y2 ? L.eb(-1, -1) : L.eb(i, y2 - 1)) : L.eb(i - 1, y2);
                i == x2 ? (y1 == y2 ? R.eb(-1, -1) : R.eb(i, y2 - 1)) : R.eb(i + 1, y2);
            }
        }
        for (int i = y2; i > y1; i -= 2) {
            if (M.empty() || M.back() != pair{x2, i}) {
                M.eb(x2, i);
                i == y2 ? (x1 == x2 ? L.eb(-1, -1) : L.eb(x2 - 1, i)) : L.eb(x2, i + 1);
                i == y1 ? (x1 == x2 ? R.eb(-1, -1) : R.eb(x2 - 1, i)) : R.eb(x2, i - 1);
            }
        }
        for (int i = x2; i > x1; i -= 2) {
            if (M.empty() || M.back() != pair{i, y1}) {
                M.eb(i, y1);
                i == x2 ? (y1 == y2 ? L.eb(-1, -1) : L.eb(i, y1 + 1)) : L.eb(i + 1, y1);
                i == x1 ? (y1 == y2 ? R.eb(-1, -1) : R.eb(i, y1 + 1)) : R.eb(i - 1, y1);
            }
        }
    }
    for (int i = 0; i < M.size(); i++) {
        auto [x, y] = M[i];
        if (b[x][y]) {
            color(L[i]);
            color(R[i]);
            for (int j = i + 1; j < M.size(); j++) {
                if (b[M[j].first][M[j].second]) {
                    color(L[j]);
                    color(R[j]);
                } else if (!check(L[i])) {
                    color(R[i]);
                }
            }
            for (int j = i - 1; j >= 0; j--) {
                if (b[M[j].first][M[j].second]) {
                    color(L[j]);
                    color(R[j]);
                } else if (!check(R[i])) {
                    color(L[i]);
                }
            }
            return 1;
        }
    }
    if (M.size() % 2 == 1) {
        return 0;
    }
    for (int i = 0; i < M.size(); i += 2) {
        color(R[i]);
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < 2 * n - 1; i++) {
        for (int j = 0; j < 2 * m - 1; j++) {
            cin >> a[i][j];
            b[i][j] = (a[i][j] == '3' || a[i][j] == '5' || a[i][j] == '8');
        }
    }
    if (!rec(0, 0, 2 * n - 2, 2 * m - 2)) {
        cout << "NO";
    } else {
        for (int i = 0; i < 2 * n - 1; i += 2) {
            for (int j = 0; j < 2 * m - 1; j += 2) {
                if (count(i, j) != a[i][j] - '0') {
                    cout << "NO";
                    return 0;
                }
            }
        }
        cout << "YES\n";
        for (int i = 0; i < 2 * n - 1; i++) {
            for (int j = 0; j < 2 * m - 1; j++) {
                cout << a[i][j];
            }
            cout << "\n";
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3460kb

input:

3 3
2.4.3
.....
5.8.5
.....
3.5.3

output:

YES
2.4#3
#####
5#8#5
#####
3#5#3

result:

ok Correct.

Test #2:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

3 3
3.4.3
.....
5.7.5
.....
3.5.3

output:

NO

result:

ok Correct.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3432kb

input:

2 2
2.2
...
2.2

output:

YES
2#2
.#.
2#2

result:

ok Correct.

Test #4:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

2 50
2.4.4.4.4.5.5.5.5.5.5.5.5.4.5.5.4.4.5.5.5.5.4.5.5.5.5.5.4.4.5.4.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.4.5.3
...................................................................................................
2.5.5.4.4.5.5.5.4.4.5.5.5.4.5.5.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.5.4.4.5.5.5.5.4...

output:

NO

result:

ok Correct.

Test #5:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

2 50
2.4.4.5.5.5.5.5.5.5.5.5.4.4.5.5.5.5.4.4.5.5.4.4.5.5.5.4.5.4.4.4.5.4.4.5.4.4.5.5.5.5.4.4.5.5.5.5.5.2
...................................................................................................
3.5.4.5.5.5.5.5.5.5.5.5.5.5.4.5.5.5.5.4.5.5.5.5.4.4.5.4.5.4.5.5.5.5.5.4.4.5.5.5.4.4.5.5.5.5.5.4...

output:

NO

result:

ok Correct.

Test #6:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

50 2
3.2
...
5.4
...
5.5
...
4.4
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.4
...
5.4
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.4
...
5.4
...
5.4
...
5.4
...
4.4
...
5.5
...
5.5
...
4.4
...
5.4
...
5.4
...
5.5
...
4.5
...
4.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
......

output:

NO

result:

ok Correct.

Test #7:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

50 2
3.3
...
5.4
...
5.4
...
5.4
...
5.4
...
5.5
...
4.4
...
4.4
...
5.5
...
4.4
...
5.5
...
5.5
...
5.5
...
5.5
...
4.5
...
5.5
...
5.5
...
5.4
...
5.4
...
5.5
...
5.4
...
5.5
...
5.4
...
5.4
...
5.5
...
5.5
...
4.5
...
4.5
...
4.5
...
4.5
...
5.5
...
5.4
...
5.4
...
5.5
...
5.5
...
4.4
...
4.4
......

output:

NO

result:

ok Correct.

Test #8:

score: -100
Wrong Answer
time: 0ms
memory: 3508kb

input:

3 50
3.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.5.5.4.4.5.5.5.5.5.5.5.5.4.4.5.5.4.4.5.4.4.5.3
...................................................................................................
4.8.8.8.8.8.8.8.8.8.8.8.8.8.8.7.7.7.7.7.7.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.7.7.8...

output:

NO

result:

wrong answer Jury has answer but participant has not.