QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103906 | #6396. Puzzle: Kusabi | kath | WA | 2ms | 3776kb | C++17 | 3.8kb | 2023-05-07 20:08:22 | 2023-05-07 20:08:26 |
Judging History
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