QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#516164 | #6398. Puzzle: Tapa | huayucaiji | RE | 0ms | 0kb | C++14 | 2.8kb | 2024-08-12 14:05:07 | 2024-08-12 14:05:07 |
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2.5e3+10;
int n,m,stp,cnt;
int a[110][110],h[MAXN],vis[MAXN],match[MAXN],b[110][110];
char mp[110][110];
char read_char() {
char ch=getchar();
while(!isdigit(ch)&&ch!='.') {
ch=getchar();
}
return ch;
}
int idx(int i,int j) {
return (i-1)*((m+1)/2)+j;
}
void repair(int &x,int &y,int idx) {
x=(idx-1)/((m+1)/2)+1;
y=(idx-1)%((m+1)/2)+1;
}
struct edge {
int v,nxt;
}e[MAXN<<3];
void addedge(int u,int v) {
e[++cnt].v=v;
e[cnt].nxt=h[u];
h[u]=cnt;
}
void insert(int u,int v) {
addedge(u,v);
addedge(v,u);
}
bool dfs(int u) {
for(int i=h[u];i;i=e[i].nxt) {
int v=e[i].v;
if(vis[v]!=stp) {
vis[v]=stp;
if(match[v]==-1||dfs(match[v])) {
match[v]=u;
//match[u]=v;
return 1;
}
}
}
return 0;
}
int main() {
cin>>n>>m;
n=2*n-1;
m=2*m-1;
int k=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
mp[i][j]=read_char();
if((i&1)&&(j&1)) {
int x=a[(i+1)/2][(j+1)/2]=mp[i][j]-'0';
if(x==2||x==4||x==7) {
k++;
b[(i+1)/2][(j+1)/2]=1;
}
}
else {
mp[i][j]='#';
}
}
}
for(int i=1;i<=(n+1)/2;i++) {
for(int j=1;j<=(m+1)/2;j++) {
int x,y;
x=i+1,y=j;
if(x<=(n+1)/2&&y<=(m+1)/2) {
if(i+x-1==2||i+x-1==n-1) {
if(j>1&&j<(m+1)/2) continue;
}
if(b[i][j]&&b[x][y]) {
insert(idx(i,j),idx(x,y));
}
}
}
for(int j=1;j<=(m+1)/2;j++) {
int x=i,y=j+1;
if(x<=(n+1)/2&&y<=(m+1)/2) {
if(y+j-1==2||y+j-1==m-1) {
if(i>1&&i<(n+1)/2) continue;
}
if(b[i][j]&&b[x][y]) {
insert(idx(i,j),idx(x,y));
}
}
}
}
fill(match+1,match+idx((n+1)/2,(m+1)/2)+1,-1);
for(int i=1;i<=idx((n+1)/2,(m+1)/2);i++) {
stp++;
k-=dfs(i);
}
if(k!=0) {
puts("NO");
return 0;
}
for(int i=1;i<=idx((n+1)/2,(m+1)/2);i++) {
int x,y;
repair(x,y,i);
if(!b[x][y]) {
continue;
}
if(match[i]==-1) {
continue;
}
if(match[match[i]]==i) {
assert(0);
}
int a,b;
repair(a,b,match[i]);
x=2*x-1;
y=2*y-1;
a=2*a-1;
b=2*b-1;
mp[(x+a)/2][(y+b)/2]='.';
}
puts("YES");
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
putchar(mp[i][j]);
}
puts("");
}
return 0;
}
/*
2 5
2.4.4.4.3
.........
3.4.4.4.2
3 2
3.3
...
4.4
...
3.3
2 2
2.3
...
3.2
5 5
3.5.5.5.3
.........
5.7.7.7.5
.........
5.7.7.7.5
.........
5.8.8.8.4
.........
3.5.5.5.2
3 3
2.4.2
.....
4.8.4
.....
2.4.2
2 2
2.2
...
2.2
*/
详细
Test #1:
score: 0
Runtime Error
input:
3 3 2.4.3 ..... 5.8.5 ..... 3.5.3