QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#259593 | #6398. Puzzle: Tapa | pakpim | WA | 0ms | 3716kb | C++20 | 3.0kb | 2023-11-21 04:26:34 | 2023-11-21 04:26:35 |
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) 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';
}
}
/*
*/
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3716kb
input:
3 3 2.4.3 ..... 5.8.5 ..... 3.5.3
output:
YES 2#4#3 ##### 5#8#5 ##### 3#5#3
result:
wrong answer Clue not satisfied at (1,1)