QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#261478#6398. Puzzle: Tapa1677118046WA 1ms4208kbC++172.7kb2023-11-22 22:12:482023-11-22 22:12:49

Judging History

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

  • [2023-11-22 22:12:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4208kb
  • [2023-11-22 22:12:48]
  • 提交

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/nn;
	ss.second=x%nn;
	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(x==1||x==2*n-1)return true;
		if(y!=j)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(!check(nx,ny,i,j))continue;
				pos[nx][ny]=!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;
			cnt+=2;
			return 1;
		}
	}
	return 0;
}
void solve(){//跑匈牙利 
	memset(pos1,-1,sizeof pos1);
	build();
	for(auto ii:A){
		vis1.clear();
		pipei(ii);
	}
	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]);
		s[(ID1.first+ID2.second)/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();	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

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

output:

NO

result:

ok Correct.

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 4208kb

input:

2 2
2.2
...
2.2

output:

NO

result:

wrong answer Jury has answer but participant has not.