QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#261792#6398. Puzzle: Tapa1677118046WA 1ms4244kbC++173.2kb2023-11-23 11:02:042023-11-23 11:02:04

Judging History

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

  • [2023-11-23 11:02:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4244kb
  • [2023-11-23 11:02:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nn=1e2+10;
char s[nn+10][nn+10];
ll getid(int x,int y){
	return x*nn+y;	
}
pair<ll,ll>getxy(ll x){
	pair<ll,ll>ss;
	ss.first=(x-1)/nn;
	ss.second=(x-1)%nn+1;
	return ss;
}
ll getnum(char x){
	return x-'0';
}
vector<ll>A;//表示进行匹配的点
vector<ll>XX[(nn+10)*(nn+10)];//图的匹配
int pos[nn+10][nn+10];//表示当前位置是匹配还是被匹配的
int vis[nn+10][nn+10];//表示当前位置是否跑过了 
int dx[]={0,0,2,-2};
int dy[]={2,-2,0,0};
int n,m;
vector<ll>B;//被匹配的点 
bool check(int x,int y,int i,int j){
	if(x<=0)return false;
	if(x>=2*n)return false;
	if(y<=0)return false;
	if(y>=2*m)return false;
	ll num=getnum(s[x][y]);
	if(num==3||num==5||num==8)return false;
	if(i==1||i==2*n-1){
		if(j==1||j==2*m-1)return true;
		if(x!=i)return false;
	}
	if(j==1||j==2*m-1){
		if(i==1||i==2*n-1)return true;
		if(y!=j)return false;
	}
	return true;
}
bool check2(int x,int y,int i,int j){
	if(x<=0)return false;
	if(x>=2*n)return false;
	if(y<=0)return false;
	if(y>=2*m)return false;
	return true;
}
ll sum;
void build(){
	cin>>n>>m;
	for(int i=1;i<2*n;i++){
		for(int j=1;j<2*m;j++){
			cin>>s[i][j];
			if(s[i][j]=='.')s[i][j]='#';
		}
	}
	for(int i=1;i<2*n;i+=2){
		for(int j=1;j<2*m;j+=2){
			ll nu=getid(i,j);
			ll num=getnum(s[i][j]);
			vis[i][j]++;
			for(int k=0;k<=3;k++){
				int nx=i+dx[k];
				int ny=j+dy[k];
				if(!check2(nx,ny,i,j))continue;
				pos[nx][ny]=1-pos[i][j];
			}
			if(num==3||num==5||num==8)continue;
			sum++;
			if(pos[i][j]==0){
				A.push_back(nu);
				for(int k=0;k<=3;k++){
					int nx=i+dx[k];
					int ny=j+dy[k];
					if(!check(nx,ny,i,j))continue;
					if(vis[nx][ny])continue;
					XX[nu].push_back(getid(nx,ny));
				}
			}else{
				B.push_back(nu);
				for(int k=0;k<=3;k++){
					int nx=i+dx[k];
					int ny=j+dy[k];
					if(!check(nx,ny,i,j))continue;
					if(vis[nx][ny])continue;
					ll an=getid(nx,ny);
					XX[an].push_back(nu);
				}
			}
		}
	}
}
ll pos1[(nn+10)*(nn+10)];//表示一个数所对应的位置
unordered_map<int, int>vis1;//匹配中避免循环
ll cnt;
int pipei(int x) {
	for (auto i : XX[x]) {
		if (vis1[i] == 1)continue;
			vis1[i] = 1;
		if (pos1[i] == -1 || pipei(pos1[i])) {
			pos1[i] = x;
			return 1;
		}
	}
	return 0;
}
void solve(){//跑匈牙利 
	memset(pos1,-1,sizeof pos1);
	build();
	for(auto ii:A){
		vis1.clear();
		pair<ll,ll>ID1=getxy(ii);
		if(pipei(ii))cnt+=2;
	}
	if(cnt!=sum){
		cout<<"NO"<<"\n";return;
	}
	cout<<"YES"<<"\n";
	for(auto ii:B){
		pair<ll,ll>ID1=getxy(ii);
		pair<ll,ll>ID2=getxy(pos1[ii]);
		if(ID1.first<=0||ID1.second<=0||ID2.first<=0||ID2.second<=0)continue;
		s[(ID1.first+ID2.first)/2][(ID1.second+ID2.second)/2]='.';
	}
	for(int i=1;i<2*n;i++){
		for(int j=1;j<2*m;j++){
			cout<<s[i][j];
		}
		cout<<"\n";
	}
	
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();	
}
/*
7 3
3.5.3
.....
5.8.4
.....
5.8.4
.....
4.8.5
.....
4.7.5
.....
5.7.5
.....
3.5.3
*/
/*
7 3
2.4.3
.....
4.7.4
.....
4.7.4
.....
4.7.4
.....
4.7.4
.....
4.7.4
.....
2.4.2
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4196kb

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: 1ms
memory: 4196kb

input:

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

output:

NO

result:

ok Correct.

Test #3:

score: 0
Accepted
time: 1ms
memory: 4040kb

input:

2 2
2.2
...
2.2

output:

YES
2#2
.#.
2#2

result:

ok Correct.

Test #4:

score: 0
Accepted
time: 1ms
memory: 3996kb

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: 0ms
memory: 4084kb

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: 1ms
memory: 4244kb

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: 4028kb

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: 0
Accepted
time: 1ms
memory: 4204kb

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...

output:

YES
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#...

result:

ok Correct.

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 4012kb

input:

3 50
2.4.4.4.5.4.4.4.4.4.4.5.5.4.4.5.5.4.4.5.5.5.4.4.5.5.5.4.4.5.5.4.4.4.4.5.5.5.5.5.5.4.4.5.5.5.5.4.4.3
...................................................................................................
5.7.7.8.7.7.7.7.8.8.8.8.7.7.8.7.7.8.8.8.8.7.7.8.8.8.7.7.8.7.7.8.8.8.8.7.7.8.8.7.7.8.8.8.7.7.8.8...

output:

YES
2.4#4.4#5#4.4#4.4#4.4#5#5#4.4#5#5#4.4#5#5#5#4.4#5#5#5#4.4#5#5#4.4#4.4#5#5#5#5#5#5#4.4#5#5#5#5#4.4#3
###################################################################################################
5#7.7#8#7.7#7.7#8#8#8#8#7.7#8#7#7#8#8#8#8#7.7#8#8#8#7#7#8#7.7#8#8#8#8#7.7#8#8#7.7#8#8#8#7.7#8#8#...

result:

wrong answer Clue not satisfied at (5,31), non-consecutive shaded cells