QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#259594 | #6398. Puzzle: Tapa | pakpim | RE | 1ms | 3600kb | C++20 | 3.2kb | 2023-11-21 04:35:59 | 2023-11-21 04:36:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ti=tuple<int,int,int>;
int a[55][55],par[55][55][2],dx[]={0,1,0,-1},dy[]={1,0,-1,0},p2[55][55][2];
vector<ti> g[55][55];
bool dt[105][105],vis[55][55];
string ans[105];
int main (){
ios::sync_with_stdio(0); cin.tie(0);
int n,m;
cin >> n >> m;
for (int i=0;i<2*n-1;i++){
for (int j=0;j<2*m-1;j++){
char c;
cin >> c;
if (c!='.') a[i/2+1][j/2+1]=c-'0',ans[i]+=c;
else ans[i]+='#';
}
}
int c1=0,c2=0;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if ((i^j)&1){
if (a[i][j]==2 || a[i][j]==4 || a[i][j]==7) c2++,g[i][j].emplace_back(n+1,m+1,1);
continue;
}
for (int k=0;k<4;k++){
int xi=i+dx[k], xj=j+dy[k];
if ((a[i][j]==2 && (a[xi][xj]==2 || a[xi][xj]==4)) or (a[i][j]==7 && a[xi][xj]==7)){
g[i][j].emplace_back(xi,xj,1);
g[xi][xj].emplace_back(i,j,0);
}
}
if (a[i][j]==4){
for (int k=-1;k<2;k+=2){
if ((i==1 || i==n) && (a[i][j+k]==2 || a[i][j+k]==4)){
g[i][j].emplace_back(i,j+k,1);
g[i][j+k].emplace_back(i,j,0);
}
else if ((j==1 || j==m) && (a[i+k][j]==2 || a[i+k][j]==4)){
g[i][j].emplace_back(i+k,j,1);
g[i+k][j].emplace_back(i,j,0);
}
}
}
if (a[i][j]==2 || a[i][j]==4 || a[i][j]==7) c1++,g[0][0].emplace_back(i,j,1);
}
}
int cnt=0;
while(1){
queue<ti> q;
q.emplace(0,0,1);
memset(vis,0,sizeof vis);
while(!q.empty()){
auto [nx,ny,nc]=q.front(); q.pop();
if (nx==n+1 && ny==m+1) break;
for (auto [xx,xy,xc]:g[nx][ny]){
if (vis[xx][xy] || xc==0) continue;
vis[xx][xy]=1;
q.emplace(xx,xy,min(nc,xc));
par[xx][xy][0]=nx;
par[xx][xy][1]=ny;
}
}
if (!q.empty()) q.pop();
if(!vis[n+1][m+1]) break;
int nx=n+1, ny=m+1;
while (nx!=0 && ny!=0){
int px=par[nx][ny][0], py=par[nx][ny][1];
if ((nx^ny)&1) p2[px][py][0]=nx,p2[px][py][1]=ny;
for (auto &[xx,xy,xc]:g[px][py]) if (xx==nx && xy==ny) xc=0;
for (auto &[xx,xy,xc]:g[nx][ny]) if (xx==px && xy==py) xc=1;
nx=px; ny=py;
}
/*for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
cout << p2[i][j][0] << ',' << p2[i][j][1] << ' ';
}
cout << '\n';
}*/
cnt++;
}
if (c1!=c2 || cnt<c1){
cout << "NO";
exit(0);
}
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (p2[i][j][0]!=0 && p2[i][j]!=0 && abs(p2[i][j][0]-i)+abs(p2[i][j][1]-j)!=1) exit(1);
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (p2[i][j][0]!=0 && p2[i][j]!=0) dt[i+p2[i][j][0]-2][j+p2[i][j][1]-2]=1;
cout << "YES\n";
for (int i=0;i<n*2-1;i++){
for (int j=0;j<m*2-1;j++){
if (dt[i][j]) cout << '.';
else cout << ans[i][j];
}
cout << '\n';
}
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3504kb
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: 3504kb
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: 3532kb
input:
2 2 2.2 ... 2.2
output:
YES 2.2 ### 2.2
result:
ok Correct.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3516kb
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: 3536kb
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: 3492kb
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: 1ms
memory: 3600kb
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
Runtime Error
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...