QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#259593#6398. Puzzle: TapapakpimWA 0ms3716kbC++203.0kb2023-11-21 04:26:342023-11-21 04:26:35

Judging History

你现在查看的是最新测评结果

  • [2023-11-21 04:26:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3716kb
  • [2023-11-21 04:26:34]
  • 提交

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';
    }
}

/*
*/

Details

Tip: Click on the bar to expand more detailed information

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)