QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#516166 | #6398. Puzzle: Tapa | FLtheLeatherman | WA | 1ms | 3916kb | C++14 | 5.2kb | 2024-08-12 14:05:17 | 2024-08-12 14:05:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef double db;
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
inline int read(){
char ch=getchar();
int x=0,f=1;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
return f>0?x:-x;
}
const int MAXN=210;
const int MAXM=MAXN*MAXN;
int n,m;
bool tag[MAXM];
bool vis[MAXN][MAXN];
char ch[MAXN][MAXN];
int ans[MAXN][MAXN];
vector<int> G[MAXN];
int trans(int i,int j){
return (i-1)*m+j;
}
pii back(int num){
int x=(num-1)/m+1,y=num-(x-1)*m;
return mp(x,y);
}
bool col[MAXM];
int tot;
int q[MAXM];
int dx[MAXM],dy[MAXM];
int mx[MAXM],my[MAXM];
bool bfs(){
bool flag=0;
int qt=0,qh=0;
rep(i,1,tot)dy[i]=0;
rep(i,1,tot){
dx[i]=0;
if(col[i]&&tag[i]&&!mx[i]){
q[qt++]=i;
}
}
while(qh<qt){
int u=q[qh++];
for(auto v: G[u]){
if(!dy[v]){
dy[v]=dx[u]+1;
if(!my[v]){
flag=true;
}
else {
dx[my[v]]=dx[u]+2;
q[qt++]=my[v];
}
}
}
}
return flag;
}
bool dfs(int u){
for(auto v: G[u]){
if(dy[v]==dx[u]+1){
dy[v]=0;
if(!my[v]||dfs(my[v])){
mx[u]=v;
my[v]=u;
return true;
}
}
}
return false;
}
void hk(){
fill(mx+1,mx+1+tot,0);
fill(my+1,my+1+tot,0);
while(bfs()){
rep(i,1,tot){
if(tag[i]&&col[i]&&!mx[i])dfs(i);
}
}
}
int main(){
n=read(),m=read();
rep(i,1,2*n-1){
scanf("%s",ch[i]+1);
if(i&1){
rep(j,1,2*m-1){
if(ch[i][j]=='2'||ch[i][j]=='4'||ch[i][j]=='7'){
vis[i][j]=true;
int _i=i/2+1,_j=j/2+1;
int x=trans(_i,_j);
tag[x]=true;
}
j++;
}
}
}
rep(j,1,m){
col[j]=j&1;
}
rep(i,2,n){
rep(j,1,m){
col[trans(i,j)]=col[trans(i-1,j)]^1;
}
}
rep(i,1,n){
rep(j,1,m){
if(i<n){
if(i==1&&j>1&&j<m);
else if(i==n-1&&j>1&&j<m);
else {
if(vis[2*i-1][2*j-1]&&vis[2*i+1][2*j-1]){
int u=trans(i,j),v=trans(i+1,j);
assert(tag[u]),assert(tag[v]);
G[u].push_back(v);
G[v].push_back(u);
}
}
}
if(j<m){
if(j==1&&i>1&&i<n);
else if(j==m-1&&i>1&&i<n);
else {
if(vis[2*i-1][2*j-1]&&vis[2*i-1][2*j+1]){
int u=trans(i,j),v=trans(i,j+1);
assert(tag[u]),assert(tag[v]);
G[u].push_back(v);
G[v].push_back(u);
}
}
}
}
}
tot=n*m;
hk();
bool flag=true;
rep(i,1,tot){
if(col[i]&&tag[i]){
if(!mx[i]){
flag=false;
break;
}
}
if(!col[i]&&tag[i]){
if(!my[i]){
flag=false;
break;
}
}
}
if(!flag)puts("NO");
else {
rep(i,1,tot){
if(!col[i])continue;
if(!tag[i])continue;
pii tmp=back(i);
int x=tmp.fi,y=tmp.se;
assert(trans(x,y)==i);
// cout<<i<<' '<<mx[i]<<endl;
if(mx[i]==i+1){
assert(my[i+1]==i);
ans[2*x-1][2*y]=true;
}
else if(mx[i]==i-1){
assert(my[i-1]==i);
ans[2*x-1][2*y-2]=true;
}
else if(mx[i]==i+m){
assert(my[i+m]==i);
ans[2*x][2*y-1]=true;
}
else if(mx[i]==i-m){
assert(my[i-m]==i);
ans[2*x-2][2*y-1]=true;
}
}
bool sb=true;
rep(i,1,2*n-1){
rep(j,1,2*m-1){
if((i&1)&&(j&1)){
int sum=ans[i-1][j-1]+ans[i-1][j]+ans[i-1][j+1]+ans[i][j-1]+ans[i][j+1]+ans[i+1][j-1]+ans[i+1][j]+ans[i+1][j+1];
// cout<<i<<' '<<j<<' '<<sum<<endl;
if(sum==1&&vis[i][j]);
else if(sum==0&&!vis[i][j]);
else sb=false;
}
}
}
// assert(sb);
puts("YES");
rep(i,1,2*n-1){
rep(j,1,2*m-1){
if((i&1)&&(j&1)){
putchar(ch[i][j]);
}
else if(ans[i][j])putchar('.');
else putchar('#');
}
putchar('\n');
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
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: 3828kb
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: 3656kb
input:
2 2 2.2 ... 2.2
output:
YES 2#2 .#. 2#2
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3816kb
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: 3740kb
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: 3852kb
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: 3756kb
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: 3824kb
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: 3688kb
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: 3900kb
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: 3916kb
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: 3764kb
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: 3744kb
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: 3760kb
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: 3888kb
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: 3896kb
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: 3820kb
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: 3864kb
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: 3820kb
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: -100
Wrong Answer
time: 1ms
memory: 3824kb
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:
wrong answer Clue not satisfied at (1,1)