QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103906#6396. Puzzle: KusabikathWA 2ms3776kbC++173.8kb2023-05-07 20:08:222023-05-07 20:08:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-07 20:08:26]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3776kb
  • [2023-05-07 20:08:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=105;
char a[N][N];
int dx[8]={1,-1,0,0,1,1,-1,-1};
int dy[8]={0,0,1,-1,-1,1,-1,1};
int ddx[4]={2,-2,0,0};
int ddy[4]={0,0,2,-2};
int id[N][N];
array<int,2>Dot[N*N];
vector<int>e[N*N];
void add1(int x,int y)
{
    e[x].push_back(y);
    e[y].push_back(x);
}
void add2(int x,int y)
{
    e[x].push_back(0);
    e[0].push_back(x);
    e[y].push_back(0);
    e[0].push_back(y);
}
void add3(int x)
{
    e[x].push_back(0);
    e[0].push_back(x);   
}
int col[N*N];
void dfs(int u,int fa)
{
    for(auto v:e[u])if(v!=fa&&v!=u)
    {
        if(col[v]==col[u]){printf("NO\n");exit(0);}
        else if(!col[v])col[v]=3-col[u],dfs(v,u);
    }
}
int vis[N*N];
void solve()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=2*n-1;++i)scanf("%s",a[i]+1);

    vector<array<int,2>>vec;
    vec.push_back({1,1});vec.push_back({1,2*m-1});
    vec.push_back({2*n-1,1});vec.push_back({2*n-1,2*m-1});
    
    int tot=0;
    for(int i=1;i<=2*n-1;++i)
    for(int j=1;j<=2*m-1;++j)
    {
        if(a[i][j]=='.'){id[i][j]=++tot;Dot[tot]={i,j};}
    }
    for(auto [x,y]:vec)
    {
        vector<int>dot;
        for(int i=0;i<4;++i)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<1||nx>2*n-1||ny<1||ny>2*m-1)continue;
            dot.push_back(id[nx][ny]);
        }
        
        if(a[x][y]=='2')add1(dot[0],dot[1]);
        else add2(dot[0],dot[1]);
    }
    
    vec.clear();
    for(int i=3;i<2*m-1;i+=2)vec.push_back({1,i}),vec.push_back({2*n-1,i});
    for(auto [x,y]:vec)
    {
        vector<int>dot;
        for(int i=2;i<4;++i)
        {
            int nx=x+dx[i],ny=y+dy[i];
            dot.push_back(id[nx][ny]);
        }
        
        if(a[x][y]=='4')add1(dot[0],dot[1]);
        else add2(dot[0],dot[1]);//cout<<"part2-->"<<dot[0]<<" "<<dot[1]<<endl;}
    }
    
    vec.clear();
    for(int i=3;i<2*n-1;i+=2)vec.push_back({i,1}),vec.push_back({i,2*m-1});
    for(auto [x,y]:vec)
    {
        vector<int>dot;
        for(int i=0;i<2;++i)
        {int nx=x+dx[i],ny=y+dy[i];dot.push_back(id[nx][ny]);}
        if(a[x][y]=='4')add1(dot[0],dot[1]);
        else add2(dot[0],dot[1]);
    }
    
    for(int i=3;i<=2*n-1;i+=2)for(int j=3;j<=2*m-1;j+=2)if(a[i][j]=='7')
    {
        vector<int>dot;
        for(int k=0;k<4;++k)
        {
            int x=i+ddx[k],y=j+ddy[k];
            if(x<=1||x>=2*n-1||y<=1||y>=2*m-1)continue;
            if(a[x][y]!='7')continue;
            int nx=i+dx[k],ny=j+dy[k];
            dot.push_back(id[nx][ny]);
        }
        if(dot.empty()){printf("NO\n");return ;}
        if(dot.size()==1)vis[dot.back()]=1;
        for(int k=0;k<dot.size();++k)for(int l=k+1;l<dot.size();++l)
        add1(dot[k],dot[l]);
    }
    else if(a[i][j]=='8')
    {
        vector<int>dot;
        for(int k=0;k<4;++k)
        {
            int nx=i+dx[k],ny=j+dy[k];
            dot.push_back(id[nx][ny]);  
        }
        for(int k=0;k<dot.size();++k)add3(dot[k]);
        
    }
    col[0]=1;dfs(0,-1);
    for(int i=1;i<=tot;++i)if(!col[i]&&vis[i])
    {
        col[i]=1;
        dfs(i,-1);
    }
    for(int i=1;i<=tot;++i)if(!col[i])
    {
        col[i]=2;
        dfs(i,-1);
    }
    
    for(int i=1;i<=tot;++i)if(col[i]==2){auto [x,y]=Dot[i];a[x][y]='#';}
    // for(int i=3;i<2*n-1;i+=2)for(int j=3;j<2*m-1;j+=2)
    // if(a[i][j]=='7')
    // {
    //     int cnt=0;
    //     for(int k=0;k<8;++k)
    //     {
    //         int x=dx[k]+i,y=dy[k]+j;
    //         cnt+=a[x][y]=='#';
    //     }
    //     if(cnt!=7){printf("NO\n");return ;}
    // }
    printf("YES\n");
    
    for(int i=1;i<=2*n-1;++i)printf("%s\n",a[i]+1);
}
int main()
{
    int T=1;
    while(T--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3776kb

input:

8
2 1 -
3 1 -
4 2 Tong
5 2 Tong
6 3 Duan
7 3 -
8 7 Chang

output:

YES
1
-
3
1
-
4
2
Tong
5
2
Tong
6
3
Duan
7

result:

wrong output format Unexpected character #10, but ' ' expected