QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253522#6398. Puzzle: TapapakpimRE 1ms3920kbC++204.0kb2023-11-17 06:36:422023-11-17 06:36:42

Judging History

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

  • [2023-11-17 06:36:42]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3920kb
  • [2023-11-17 06:36:42]
  • 提交

answer

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

using pi=pair<int,int>;
int a[55][55],dg[55][55];
vector<pi> g[55][55];
queue <pi> q;
bool vis[55][55],dt[105][105];
string ans[105];

int main (){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m;
    cin >> n >> m;
    for (int i=0;i<2*n-1;i++){
        for (int j=0;j<2*m-1;j++){
            char c;
            cin >> c;
            if (c!='.') a[i/2+1][j/2+1]=c-'0',ans[i]+=c;
            else ans[i]+='#';
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            for (int k=0;k<2;k++){
                int xi=i-(k&1), xj=j-((k+1)&1);
                if ((a[i][j]==2 && (a[xi][xj]==2 || a[xi][xj]==4)) or (a[i][j]==7 && a[xi][xj]==7)){
                    g[i][j].emplace_back(xi,xj);
                    g[xi][xj].emplace_back(i,j);
                }
            }
            if (a[i][j]==4){
                if ((i==1 || i==n) && (a[i][j-1]==2 || a[i][j-1]==4)){
                    g[i][j].emplace_back(i,j-1);
                    g[i][j-1].emplace_back(i,j);
                }
                else if ((j==1 || j==m) && (a[i-1][j]==2 || a[i-1][j]==4)){
                    g[i][j].emplace_back(i-1,j);
                    g[i-1][j].emplace_back(i,j);
                }
            }
        }
    }
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) dg[i][j]=g[i][j].size();
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (vis[i][j]) continue;
            if ((a[i][j]==2 || a[i][j]==4 || a[i][j]==7) && dg[i][j]==0){
                cout << "NO";
                exit(0);
            }
            if (dg[i][j]==1){
                q.emplace(i,j);
                while (!q.empty()){
                    auto [ni,nj]=q.front();
                    q.pop();
                    if (vis[i][j]) continue;
                    vis[i][j]=1;
                    for (auto [ci,cj]:g[ni][nj]){
                        if (!vis[ci][cj]){
                            vis[ci][cj]=1;
                            dt[ni+ci-2][nj+cj-2]=1;
                            for (auto [xi,xj]:g[ci][cj]){
                                if (vis[xi][xj]) continue;
                                dg[xi][xj]--;
                                if (dg[xi][xj]==1) q.emplace(xi,xj);
                                if (dg[xi][xj]==0){
                                    cout << "NO";
                                    exit(0);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (vis[i][j]) continue;
            if (a[i][j]==2 || a[i][j]==4 || a[i][j]==7){
                q.emplace(i,j);
                while (!q.empty()){
                    auto [ni,nj]=q.front();
                    q.pop();
                    if (vis[i][j]) continue;
                    vis[i][j]=1;
                    for (auto [ci,cj]:g[ni][nj]){
                        if (!vis[ci][cj]){
                            vis[ci][cj]=1;
                            dt[ni+ci-2][nj+cj-2]=1;
                            for (auto [xi,xj]:g[ci][cj]){
                                if (vis[xi][xj]) continue;
                                dg[xi][xj]--;
                                if (dg[xi][xj]==1) q.emplace(xi,xj);
                                if (dg[xi][xj]==0){
                                    cout << "NO";
                                    exit(1);
                                }
                            }
                            break;
                        }
                    }
                }
            }
        }
    }
    cout << "YES\n";
    for (int i=0;i<n*2-1;i++){
        for (int j=0;j<m*2-1;j++){
            if (dt[i][j]) cout << '.';
            else cout << ans[i][j];
        }
        cout << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3676kb

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: 0ms
memory: 3676kb

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: 3920kb

input:

2 2
2.2
...
2.2

output:

YES
2.2
###
2.2

result:

ok Correct.

Test #4:

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

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: 3572kb

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: 3708kb

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: 3852kb

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: 0
Accepted
time: 0ms
memory: 3616kb

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:

YES
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#...

result:

ok Correct.

Test #9:

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

input:

3 50
2.4.4.4.5.4.4.4.4.4.4.5.5.4.4.5.5.4.4.5.5.5.4.4.5.5.5.4.4.5.5.4.4.4.4.5.5.5.5.5.5.4.4.5.5.5.5.4.4.3
...................................................................................................
5.7.7.8.7.7.7.7.8.8.8.8.7.7.8.7.7.8.8.8.8.7.7.8.8.8.7.7.8.7.7.8.8.8.8.7.7.8.8.7.7.8.8.8.7.7.8.8...

output:

YES
2.4#4.4#5#4.4#4.4#4.4#5#5#4.4#5#5#4.4#5#5#5#4.4#5#5#5#4.4#5#5#4.4#4.4#5#5#5#5#5#5#4.4#5#5#5#5#4.4#3
###################################################################################################
5#7.7#8#7.7#7.7#8#8#8#8#7.7#8#7.7#8#8#8#8#7.7#8#8#8#7.7#8#7.7#8#8#8#8#7.7#8#8#7.7#8#8#8#7.7#8#8#...

result:

ok Correct.

Test #10:

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

input:

50 3
3.5.3
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
5.8.4
.....
5.8.4
.....
4.8.5
.....
4.7.5
.....
5.7.5
.....
5.8.5
.....
5.8.4
.....
5.8.4
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
4.8.5
.....
4.7.5
.....
5.7.5
.....
5.8.5
.....
5.8.5
.....
5.8.5
....

output:

YES
3#5#3
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
5#8#4
####.
5#8#4
#####
4#8#5
.####
4#7#5
##.##
5#7#5
#####
5#8#5
#####
5#8#4
####.
5#8#4
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
4#8#5
.####
4#7#5
##.##
5#7#5
#####
5#8#5
#####
5#8#5
#####
5#8#5
##...

result:

ok Correct.

Test #11:

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

input:

50 3
2.4.3
.....
4.8.5
.....
4.8.5
.....
5.8.5
.....
4.7.4
.....
4.7.4
.....
4.8.5
.....
4.8.4
.....
5.8.4
.....
4.7.5
.....
4.7.5
.....
5.8.5
.....
5.8.5
.....
5.8.4
.....
5.8.4
.....
5.8.5
.....
5.8.5
.....
5.7.5
.....
5.7.5
.....
5.8.5
.....
5.8.5
.....
5.8.5
.....
4.8.5
.....
4.7.5
.....
4.7.4
....

output:

YES
2.4#3
#####
4#8#5
.####
4#8#5
#####
5#8#5
#####
4#7#4
.#.#.
4#7#4
#####
4#8#5
.####
4#8#4
####.
5#8#4
#####
4#7#5
.#.##
4#7#5
#####
5#8#5
#####
5#8#5
#####
5#8#4
####.
5#8#4
#####
5#8#5
#####
5#8#5
#####
5#7#5
##.##
5#7#5
#####
5#8#5
#####
5#8#5
#####
5#8#5
#####
4#8#5
.####
4#7#5
##.##
4#7#4
.#...

result:

ok Correct.

Test #12:

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

input:

10 10
2.4.4.4.5.5.4.4.5.2
...................
5.7.8.8.7.8.7.7.8.4
...................
4.7.8.8.7.8.8.8.8.5
...................
4.8.8.8.7.7.8.8.8.4
...................
5.8.7.7.7.7.8.8.7.4
...................
4.7.7.8.8.8.8.8.7.4
...................
4.8.7.8.8.7.7.7.8.4
...................
5.8.7.8.8.7.8....

output:

YES
2.4#4.4#5#5#4.4#5#2
##################.
5#7#8#8#7#8#7.7#8#4
##.#####.##########
4#7#8#8#7#8#8#8#8#5
.##################
4#8#8#8#7.7#8#8#8#4
##################.
5#8#7.7#7.7#8#8#7#4
################.##
4#7.7#8#8#8#8#8#7#4
.#################.
4#8#7#8#8#7#7.7#8#4
####.#####.########
5#8#7#8#8#7#8#8#...

result:

ok Correct.

Test #13:

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

input:

10 10
3.5.5.5.5.5.5.4.4.3
...................
5.7.7.8.8.7.8.7.7.4
...................
5.8.8.7.7.7.7.7.8.4
...................
5.8.7.7.8.8.8.7.7.5
...................
5.8.8.7.7.7.7.7.7.5
...................
4.7.7.8.8.7.8.8.7.4
...................
4.7.7.7.7.7.7.8.7.4
...................
5.8.7.8.7.7.7....

output:

NO

result:

ok Correct.

Test #14:

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

input:

10 10
2.4.5.4.4.5.5.5.5.3
...................
4.8.7.7.8.8.8.7.8.4
...................
4.8.7.8.7.8.8.7.8.4
...................
5.7.7.8.7.7.7.8.7.5
...................
5.7.8.8.8.8.8.8.7.5
...................
4.7.8.7.7.7.8.8.8.5
...................
4.7.7.7.8.7.7.8.8.5
...................
4.7.8.7.8.8.7....

output:

YES
2.4#5#4.4#5#5#5#5#3
###################
4#8#7.7#8#8#8#7#8#4
.#############.###.
4#8#7#8#7#8#8#7#8#4
####.###.##########
5#7#7#8#7#7.7#8#7#5
##.#############.##
5#7#8#8#8#8#8#8#7#5
###################
4#7#8#7.7#7#8#8#8#5
.#.#######.########
4#7#7.7#8#7#7#8#8#5
############.######
4#7#8#7#8#8#7#8#...

result:

ok Correct.

Test #15:

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

input:

10 10
2.4.4.4.5.5.4.4.5.3
...................
5.7.8.8.7.7.7.7.7.5
...................
5.7.7.7.8.7.7.8.7.5
...................
4.8.7.7.8.8.8.7.8.4
...................
4.8.8.8.7.8.8.7.8.4
...................
4.8.8.8.7.8.8.8.8.5
...................
4.8.7.8.7.7.7.8.8.4
...................
5.8.7.8.7.8.8....

output:

YES
2.4#4.4#5#5#4.4#5#3
###################
5#7#8#8#7.7#7.7#7#5
##.#############.##
5#7#7.7#8#7.7#8#7#5
###################
4#8#7.7#8#8#8#7#8#4
.#############.###.
4#8#8#8#7#8#8#7#8#4
########.##########
4#8#8#8#7#8#8#8#8#5
.##################
4#8#7#8#7#7.7#8#8#4
####.###.#########.
5#8#7#8#7#8#8#8#...

result:

ok Correct.

Test #16:

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

input:

10 10
3.5.4.4.5.5.4.4.5.3
...................
5.7.8.8.7.8.8.8.8.5
...................
5.7.8.8.7.7.7.8.8.5
...................
5.8.7.7.8.8.7.8.8.5
...................
5.8.8.8.8.8.7.8.8.4
...................
5.7.7.8.8.7.8.7.8.4
...................
5.7.8.8.8.7.7.7.8.5
...................
5.7.8.8.8.8.7....

output:

YES
3#5#4.4#5#5#4.4#5#3
###################
5#7#8#8#7#8#8#8#8#5
##.#####.##########
5#7#8#8#7#7.7#8#8#5
###################
5#8#7.7#8#8#7#8#8#5
############.######
5#8#8#8#8#8#7#8#8#4
##################.
5#7.7#8#8#7#8#7#8#4
##########.###.####
5#7#8#8#8#7#7#7#8#5
##.#########.######
5#7#8#8#8#8#7#8#...

result:

ok Correct.

Test #17:

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

input:

10 10
3.5.5.4.4.5.5.4.4.3
...................
5.7.7.7.7.8.8.7.7.5
...................
5.8.7.7.8.8.8.8.8.5
...................
5.7.8.8.8.7.7.8.8.4
...................
5.7.7.7.8.7.7.8.7.4
...................
5.8.8.8.7.7.8.8.7.5
...................
4.7.7.8.8.8.7.7.8.5
...................
4.8.8.8.7.7.8....

output:

YES
3#5#5#4.4#5#5#4.4#3
###################
5#7.7#7.7#8#8#7.7#5
###################
5#8#7.7#8#8#8#8#8#5
###################
5#7#8#8#8#7.7#8#8#4
##.###############.
5#7#7.7#8#7.7#8#7#4
################.##
5#8#8#8#7.7#8#8#7#5
###################
4#7.7#8#8#8#7.7#8#5
.##################
4#8#8#8#7.7#8#7#...

result:

ok Correct.

Test #18:

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

input:

10 10
2.4.4.5.4.4.4.4.4.2
...................
4.8.7.8.8.7.8.8.8.4
...................
4.8.7.8.7.7.7.7.7.4
...................
4.7.7.8.7.8.7.7.7.4
...................
5.8.7.8.7.7.8.8.8.4
...................
4.8.7.8.7.7.7.7.7.5
...................
4.8.7.7.8.8.7.7.7.5
...................
4.7.7.8.8.7.8....

output:

YES
2#4.4#5#4.4#4.4#4.2
.##################
4#8#7#8#8#7#8#8#8#4
####.#####.#######.
4#8#7#8#7#7#7.7#7#4
.#######.#######.##
4#7.7#8#7#8#7.7#7#4
##################.
5#8#7#8#7.7#8#8#8#4
####.##############
4#8#7#8#7.7#7.7#7#5
.###############.##
4#8#7.7#8#8#7.7#7#5
###################
4#7.7#8#8#7#8#8#...

result:

ok Correct.

Test #19:

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

input:

10 10
2.4.4.4.4.4.4.4.4.2
...................
4.8.8.7.7.7.7.8.8.5
...................
4.7.8.7.8.8.7.8.7.4
...................
4.7.8.7.7.8.7.7.7.4
...................
4.8.7.8.7.7.7.7.8.4
...................
4.8.7.8.7.7.7.7.7.4
...................
4.7.8.7.8.7.7.7.7.4
...................
4.7.7.7.7.7.7....

output:

YES
2.4#4.4#4.4#4.4#4.2
###################
4#8#8#7.7#7.7#8#8#5
.##################
4#7#8#7#8#8#7#8#7#4
##.###.#####.###.#.
4#7#8#7#7#8#7#7#7#4
.#######.#####.####
4#8#7#8#7#7.7#7#8#4
####.#############.
4#8#7#8#7.7#7.7#7#4
.###############.##
4#7#8#7#8#7.7#7#7#4
##.###.#######.###.
4#7#7#7#7#7.7#7#...

result:

ok Correct.

Test #20:

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

input:

50 50
3.5.5.5.5.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.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.3
...................................................................................................
5.8.8.8.8.7.7.8.8.8.8.8.7.7.8.8.8.7.7.7.8.8.8.8.8.8.8.8.8.8.8.7.8.8.8.7.7.8.8.8.8.8.8.8.8.7.8....

output:

YES
3#5#5#5#5#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#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#5#3
###################################################################################################
5#8#8#8#8#7.7#8#8#8#8#8#7.7#8#8#8#7#7.7#8#8#8#8#8#8#8#8#8#8#8#7#8#8#8#7.7#8#8#8#8#8#8#8#8#7#8#7....

result:

ok Correct.

Test #21:

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

input:

50 50
3.5.5.5.4.4.5.5.5.5.5.5.5.5.5.5.5.5.4.4.5.4.4.4.4.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.3
...................................................................................................
4.8.8.8.8.8.8.7.7.8.8.8.8.8.8.8.8.8.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.8.8.8....

output:

NO

result:

ok Correct.

Test #22:

score: -100
Runtime Error

input:

50 50
3.5.4.4.5.5.5.5.4.4.5.4.4.5.5.4.4.5.5.5.5.5.5.4.4.5.5.5.5.5.5.4.4.5.5.4.4.5.5.5.5.5.5.5.5.5.5.5.5.3
...................................................................................................
5.7.7.8.8.8.7.7.7.8.8.8.8.8.7.8.8.8.8.8.8.8.8.8.8.7.7.8.8.7.7.8.8.8.8.8.8.8.8.8.7.7.8.8.8.8.7....

output:

NO

result: