QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#370869 | #6398. Puzzle: Tapa | ricofx# | WA | 1ms | 3852kb | C++17 | 3.4kb | 2024-03-29 18:11:37 | 2024-03-29 18:11:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define enl putchar('\n')
const int MAXN = 55;
int n,m;
char c;
int a[MAXN][MAXN],b[MAXN][MAXN];
int id[MAXN][MAXN],idtot=0;
struct EG{
int to,nxt;
}e[MAXN*MAXN*2];
int head[MAXN*MAXN],etot;
inline void add(int u,int v){
int x=(u-1)/m+1,y=(u-1)%m+1;
// printf("%d %d\n",x,y);
if((x+y)&1)swap(u,v);
// printf("%d %d\n",u,v);
e[etot]={v,head[u]};
head[u]=etot++;
}
int vis[MAXN*MAXN],mat[MAXN*MAXN];
vector<int>path;
bool dfs(int u){
for(int i=head[u];~i;i=e[i].nxt){
int v=e[i].to;
if(!vis[v]){
path.push_back(v);
vis[v]=1;
if(mat[v]==0||dfs(mat[v])){
mat[v]=u;
return true;
}
}
}
return false;
}
void clear(){
for(auto &pos:path)vis[pos]=0;
path.clear();
}
char op[MAXN<<1][MAXN<<1];
int main() {
ios::sync_with_stdio(0);cin.tie(0);
memset(head,-1,sizeof(head));
int ans=0,sum=0;
cin >> n >> m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
int bas=3;
if(i!=1&&i!=n)bas+=2;
if(j!=1&&j!=m)bas+=2;
if(bas==7)++bas;
cin>>b[i][j];
a[i][j]=bas-b[i][j];
sum+=a[i][j];
id[i][j]=++idtot;
if(j!=m)cin>>c;
}
if(i!=n)for(int j=1;j<m<<1;++j)cin>>c;
}
// printf("sum = %d\n",sum);
// for(int i=1;i<=n;++i,enl)
// for(int j=1;j<=m;++j)
// printf("%d ",a[i][j]);
if(sum & 1)return !printf("NO\n");
for(int i=1;i<n;++i){
if(a[i][1] && a[i+1][1])
add(id[i][1],id[i+1][1]);
if(a[i][m] && a[i+1][m])
add(id[i][m],id[i+1][m]);
}
for(int i=1;i<m;++i){
if(a[1][i] && a[1][i+1])
add(id[1][i],id[1][i+1]);
// printf("a[%d][%d]=%d check = %d \n",n,i,a[n][i],a[n][i] && a[n][i+1]);
if(a[n][i] && a[n][i+1])
add(id[n][i],id[n][i+1]);
}
for(int i=1;i<=n;++i){
ans+=dfs(id[i][1]);clear();
ans+=dfs(id[i][m]);clear();
}
for(int i=1;i<=m;i+=2){
ans+=dfs(id[1][i]);clear();
ans+=dfs(id[n][i]);clear();
}
// printf("ans = %d\n",ans);
for(int i=2;i<n;++i)
for(int j=2;j<m;++j){
if(i+1!=n && a[i][j] && a[i+1][j])
add(id[i][j],id[i+1][j]);
if(j+1!=m && a[i][j] && a[i][j+1])
add(id[i][j],id[i][j+1]);
}
for(int i=2;i<n;++i)
for(int j=2;j<m;++j){
if((i+j)&1)continue;
ans+=dfs(id[i][j]);
clear();
}
if(ans*2!=sum)return !printf("NO\n");
printf("YES\n");
for(int i=1;i<n<<1;++i)
for(int j=1;j<m<<1;++j)
op[i][j]='#';
for(int i=1;i<=idtot;++i)
if(mat[i]){
// printf("conn %d %d\n",i,mat[i]);
int x1=(i-1)/m+1,y1=(i-1)%m+1;
int x2=(mat[i]-1)/m+1,y2=(mat[i]-1)%m+1;
x1=x1*2-1;
x2=x2*2-1;
y1=y1*2-1;
y2=y2*2-1;
op[(x1+x2)/2][(y1+y2)/2]='.';
}
for(int i=1;i<n<<1;++i,enl)
for(int j=1;j<m<<1;++j)
if( (i&1) && (j&1) ){
printf("%d",b[(i+1)/2][(j+1)/2]);
}else{
printf("%c",op[i][j]);
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3852kb
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: 3808kb
input:
2 2 2.2 ... 2.2
output:
YES 2.2 ### 2.2
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3796kb
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: 3680kb
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: 3760kb
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: 3824kb
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: 3812kb
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 (5,1)