QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310417#6398. Puzzle: TapaPlentyOfPenaltyWA 0ms3800kbC++206.5kb2024-01-21 13:14:262024-01-21 13:14:27

Judging History

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

  • [2024-01-21 13:14:27]
  • 评测
  • 测评结果：WA
  • 用时：0ms
  • 内存：3800kb
查看
  • [2024-01-21 13:14:26]
  • 提交

answer

#include<bits/stdc++.h>
#define QUIT exit((puts("NO"),0))
using namespace std;
const int N=100;
int n,m,mp[N+10][N+10],tv[N+10][N+10],fl,vis[N+10][N+10],TIM;
char tmp[N+10][N+10],prt[N+10][N+10];
const int w[4][2]={{2,0},{-2,0},{0,2},{0,-2}};
bool dfs(int x,int y,int tx,int ty){
	if(x==tx&&y==ty)return 1;
	vis[x][y]=TIM;
	int ttx,tty;
	int ret=0;
	for(int k=0;k<4;++k){
		ttx=x+w[k][0],tty=y+w[k][1];
		if(tx<3||tx>(n-1<<1)||ty<3||ty>(m-1<<1))continue;
		if(vis[ttx][tty]!=TIM&&mp[ttx][tty])ret|=dfs(ttx,tty,tx,ty);
	}
	return ret;
}
void Solve(int xl,int yl,int xr,int yr){
	if(xl!=1){
		//cout<<"?\n";
		for(int i=xl;i<=xr;++i)for(int j=yl;j<=yr;++j)if(!(i&1)||!(j&1))prt[i][j]='#';
		int tg=1,md,mx,my,wy,td,tx,ty,tw;
		while(tg){
			tg=0;
			md=4;
			for(int i=xl;i<=xr;i+=2)for(int j=yl;j<=yr;j+=2)if(mp[i][j]){
				//cout<<"FIND "<<i<<" "<<j<<"\n";
				td=0;
				tg=1;
				for(int k=0;k<4;++k){
					tx=i+w[k][0],ty=j+w[k][1];
					if(tx<xl||tx>xr||ty<yl||ty>yr)continue;
					if(mp[tx][ty])tw=k,++td;
				}
				//cout<<"TD="<<td<<"\n";
				if(td<md)md=td,mx=i,my=j,wy=tw;
			}
			if(!tg)break;
			if(!md)QUIT;
			//cout<<"("<<mx<<","<<my<<") and ("<<mx+w[wy][0]<<" "<<my+w[wy][1]<<")\n";
			if(md==1){
				mp[mx][my]=mp[mx+w[wy][0]][my+w[wy][1]]=0;
				prt[mx+(w[wy][0]>>1)][my+(w[wy][1]>>1)]='.';
				continue;
			}
			int w1,w2;
			for(int i=xl;i<=xr;i+=2)for(int j=yl;j<=yr;j+=2)if(mp[i][j]){
				td=0;
				tg=1;
				w1=w2=0;
				for(int k=0;k<4;++k){
					tx=i+w[k][0],ty=j+w[k][1];
					if(tx<xl||tx>xr||ty<yl||ty>yr)continue;
					if(mp[tx][ty])++td,w1?w2=k:w1=k;
				}
				//cout<<"TD="<<td<<"\n";
				++TIM;
				mp[i][j]=0;
				if(td==2&&dfs(i+w[w1][0],j+w[w1][1],i+w[w2][0],j+w[w2][1])){
					mx=i,my=j,wy=w1;
					mp[i][j]=1;
					break;
				}
				mp[i][j]=1;
			}
			mp[mx][my]=mp[mx+w[wy][0]][my+w[wy][1]]=0;
			prt[mx+(w[wy][0]>>1)][my+(w[wy][1]>>1)]='.';
		}
		//cout<<"DONE.\n";
		return;
	}
	if(xr==xl){
		if(yr==yl){
			if(mp[xl][yl])QUIT;
			return;
		}
		for(int i=yl+1;i<yr;i+=2){
			if(mp[xl][i-1]){
				prt[xl][i]='.';
				if(!mp[xl][i+1])QUIT;
				mp[xl][i+1]=0;
			}else prt[xl][i]='#';
		}
		return;
	}
	if(xr-xl==2)for(int j=yl+1;j<yr;++j)prt[xl+1][j]='#';
	else{
		for(int i=xl+1;i<xr;++i)prt[i][yl+1]=prt[i][yr-1]='#';
		for(int i=yl+1;i<yr;++i)prt[xl+1][i]=prt[xr-1][i]='#';
		Solve(xl+2,yl+2,xr-2,yr-2);
	}
	//cout<<"SOLVE["<<xl<<","<<xr<<"] ["<<yl<<","<<yr<<"]\n";
	for(int i=xl;i<=xr;++i)tv[i][yl]=mp[i][yl],tv[i][yr]=mp[i][yr];
	for(int i=yl;i<=yr;++i)tv[xl][i]=mp[xl][i],tv[xr][i]=mp[xr][i];
	//for(int i=xl;i<=xr;++i,puts(""))for(int j=yl;j<=yr;++j)cout<<(char)(tv[i][j]+'0');
	for(int i=xl+1;i<xr;i+=2){
		if(tv[i-1][yl]){
			tv[i-1][yl]=0;
			prt[i][yl]='.';
			//cout<<"DEL "<<i<<" "<<yl<<"\n";
			if(!tv[i+1][yl])goto Skip;
			tv[i+1][yl]=0;
		}else prt[i][yl]='#';
	}
	for(int i=yl+1;i<yr;i+=2){
		if(tv[xr][i-1]){
			tv[xr][i-1]=0;
			prt[xr][i]='.';
			//cout<<"DEL "<<xr<<" "<<i<<"\n";
			if(!tv[xr][i+1])goto Skip;
			tv[xr][i+1]=0;
		}else prt[xr][i]='#';
	}
	for(int i=xr-1;i>xl;i-=2){
		if(tv[i+1][yr]){
			tv[i+1][yr]=0;
			prt[i][yr]='.';
			//cout<<"DEL "<<i<<" "<<yr<<"\n";
			if(!tv[i-1][yr])goto Skip;
			tv[i-1][yr]=0;
		}else prt[i][yr]='#';
	}
	for(int i=yr-1;i>yl;i-=2){
		if(tv[xl][i+1]){
			tv[xl][i+1]=0;
			prt[xl][i]='.';
			if(!tv[xl][i-1])goto Skip;
			tv[xl][i-1]=0;
		}else prt[xl][i]='#';
	}
	return;
	Skip:
	//cout<<"SKIP.\n";
	for(int i=xl;i<=xr;++i)tv[i][yl]=mp[i][yl],tv[i][yr]=mp[i][yr];
	for(int i=yl;i<=yr;++i)tv[xl][i]=mp[xl][i],tv[xr][i]=mp[xr][i];
	//for(int i=xl;i<=xr;++i,puts(""))for(int j=yl;j<=yr;++j)cout<<(char)(tv[i][j]+'0');
	for(int i=yl+1;i<yr;i+=2){
		if(tv[xl][i-1]){
			tv[xl][i-1]=0;
			prt[xl][i]='.';
			if(!tv[xl][i+1])QUIT;
			tv[xl][i+1]=0;
		}else prt[xl][i]='#';
	}
	for(int i=xl+1;i<xr;i+=2){
		if(tv[i-1][yr]){
			tv[i-1][yr]=0;
			prt[i][yr]='.';
			if(!tv[i+1][yr])QUIT;
			tv[i+1][yr]=0;
		}else prt[i][yr]='#';
	}
	for(int i=yr-1;i>yl;i-=2){
		if(tv[xr][i+1]){
			tv[xr][i+1]=0;
			prt[xr][i]='.';
			if(!tv[xr][i-1])QUIT;
			tv[xr][i-1]=0;
		}else prt[xr][i]='#';
	}
	for(int i=xr-1;i>xl;i-=2){
		if(tv[i+1][yl]){
			tv[i+1][yl]=0;
			prt[i][yl]='.';
			if(!tv[i-1][yl])QUIT;
			tv[i-1][yl]=0;
		}else prt[i][yl]='#';
	}
}
const int d[8][2]={{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1}};
int main(){
	freopen("1.in","r",stdin);
	//cin.sync_with_stdio(0),cin.tie(0);
	//cin>>n>>m;
	scanf("%d%d",&n,&m);
	if(n>m)swap(n,m),fl=1;
	if(fl){
		for(int i=1;i<(m<<1);++i)scanf("%s",tmp[i]+1);
		for(int i=1;i<(n<<1);++i)for(int j=1;j<(m<<1);++j)mp[i][j]=tmp[j][i]-'0',prt[i][j]=tmp[j][i];
	}else{
		for(int i=1;i<(n<<1);++i)scanf("%s",tmp[i]+1);
		for(int i=1;i<(n<<1);++i)for(int j=1;j<(m<<1);++j)mp[i][j]=tmp[i][j]-'0',prt[i][j]=tmp[i][j];
	}
	for(int i=1;i<(n<<1);i+=2)for(int j=1;j<(m<<1);j+=2)mp[i][j]=(mp[i][j]==2||mp[i][j]==4||mp[i][j]==7);
	Solve(1,1,(n<<1)-1,(m<<1)-1);
	puts("YES");
	if(fl){
		for(int i=1;i<(m<<1);++i){
			for(int j=1;j<(n<<1);++j)putchar(prt[j][i]);
			putchar('\n');
		}
	}else{
		for(int i=1;i<(n<<1);++i){
			for(int j=1;j<(m<<1);++j)putchar(prt[i][j]);
			putchar('\n');
		}
	}
	int tot,tg,ls;
	for(int i=1;i<(n<<1);i+=2)for(int j=1;j<(m<<1);j+=2){
		tot=0,tg=0,ls=-1;
		//cout<<"in ("<<i<<","<<j<<")\n";
		for(int k=0;k<8;++k)if(i+d[k][0]>0&&i+d[k][0]<(n<<1)&&j+d[k][1]>0&&j+d[k][1]<(m<<1)){
			//cout<<"("<<i+d[k][0]<<","<<j+d[k][1]<<")\n";
			if(prt[i+d[k][0]][j+d[k][1]]=='#'){
				++tot;
				if(ls!=1)++tg,ls=1;
			}else{
				if(ls)++tg,ls=0;
			}
		}else if(ls)++tg,ls=0;
		//cout<<"TT="<<tot<<"p="<<prt[i][j]<<"\n";
		assert(tot==prt[i][j]-'0');
		assert(tg<=3);
	}
	return 0;
}
/*
3 3
2.4.3
.....
5.7.5
.....
3.5.3

3 3
3.4.3
.....
5.7.5
.....
3.5.3

2 3
2.4.2
.....
2.4.2

3 2
3.3
...
5.5
...
3.3

4 4
3.5.5.3
.......
5.7.8.5
.......
5.7.7.5
.......
3.5.5.3

5 4
2.4.5.3
.......
5.7.7.5
.......
5.7.7.4
.......
5.7.7.4
.......
3.4.4.3

4 5
2.4.5.4.2
.........
4.8.8.8.4
.........
4.8.8.8.4
.........
2.4.4.4.3

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.8.8.8.7.7.7.8.4
...................
4.8.8.8.8.7.8.7.7.5
...................
4.8.8.8.8.8.8.8.8.5
...................
3.5.4.4.5.5.4.4.4.2
*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3800kb

input:

3 3
2.4.3
.....
5.8.5
.....
3.5.3

output:

YES

result:

wrong output format Unexpected end of file - token expected
English 繁體中文 简体中文

Server Time: 2024-12-02 22:52:26 | OpenSource Project