QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#253520	#6398. Puzzle: Tapa	pakpim	WA	1ms	3604kb	C++20	4.2kb	2023-11-17 06:32:06	2023-11-17 06:32:07

Judging History

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

[2023-11-17 06:32:07]
评测

测评结果：WA
用时：1ms
内存：3604kb

查看

[2023-11-17 06:32:06]
提交

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);
                                }
                            }
                        }
                        break;
                    }
                }
            }
        }
    }
    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 (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';
    }
}

/*
*/

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3548kb

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

input:

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

output:

NO

result:

ok Correct.

Test #3:

score: 0

Accepted

time: 1ms

memory: 3468kb

input:

2 2
2.2
...
2.2

output:

YES
2.2
###
2.2

result:

ok Correct.

Test #4:

score: 0

Accepted

time: 0ms

memory: 3548kb

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: 1ms

memory: 3488kb

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: 1ms

memory: 3520kb

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: 1ms

memory: 3604kb

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

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:

wrong answer Clue not satisfied at (3,35)