列表

详情

NC221006. 拱桥(Easy Version)

描述

本题有Easy,Hard两个版本，两个版本之间的区别仅在数据范围，通过Hard Version的代码可以直接通过Easy Version。保证Easy Version的测试用例集是Hard Version的子集


现在有一个（n行m列，最左上角的坐标为1,1）的棋盘，你要在上面修建一些拱桥。
众所周知，修建一座拱桥需要两个桥墩，我们规定两个桥墩之间的欧几里得距离应该在之间。
棋盘上面恰好有一个格子是坏掉的，你不能在坏掉的格子上面修建任何桥墩（但是允许有拱桥跨过此格）
你只能将桥墩修建在格子的正中心，且每个格子只能修建唯一的一个桥墩。
你并不需要担心修建的桥之间由于交叉导致冲突的问题，实际上，你可以通过修建不同高度的桥来避免它们冲突。

你想要尽可能多的在棋盘上面修建拱桥，请你给出一个修建拱桥数目最多的方案。

输入描述

首先输入一个正整数表示有T组测试案例，对于每组测试案例：
第一行输入两个正整数表示棋盘的大小是n行m列。
第二行输入一个坐标

输出描述

对于每组测试案例：
输出n行，每行m个数字。每个坐标上的数字表示桥墩属于哪一座桥，一座桥有两个桥墩。
你可以用俩个相同的正整数表示一座桥，注意同一座桥的两个桥墩之间的欧几里得距离应该在之间。
如果某个格子上没有桥墩，则在该位置输出“-1”。

请保证坐标上的数字为“-1”。

示例1

输入: 

1
3 3
2 2

输出: 

1 2 3
3 -1 1
4 2 4

说明:

构造方案如题面上的图片所示。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 27ms, 内存消耗: 528K, 提交时间: 2021-10-15 21:55:02 

#include<bits/stdc++.h>
using namespace std;
int H,W,p,q,n,mch[405],vst[405],sign,a[405];
vector<int> g[405];
bool dfs(int x){
	vst[x]=sign,random_shuffle(g[x].begin(),g[x].end());
	for(int y:g[x]){
		int t=mch[y];
		if(vst[t]==sign)continue;
		mch[y]=x,mch[x]=y,mch[t]=0;
		if(!t||dfs(t))return 1;
		mch[y]=t,mch[t]=y,mch[x]=0;
	}
	return 0;
}
int pos(int x,int y){
	return (x-1)*W+y;
}
void A(int x,int y){
	if(x==pos(p,q)||y==pos(p,q))return ;
	g[x].push_back(y),g[y].push_back(x);
}
void Solve(){
	scanf("%d%d%d%d",&H,&W,&p,&q);
	srand(23333),n=H*W;
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			if(j+2<=W)A(pos(i,j),pos(i,j+2));
			if(j+2<=W&&i+1<=H)A(pos(i,j),pos(i+1,j+2));
			if(j+1<=W&&i+2<=H)A(pos(i,j),pos(i+2,j+1));
			if(i+2<=H)A(pos(i,j),pos(i+2,j));
		}
	}
	int ans=0;
	for(int t=1;t<=10;t++)for(int i=1;i<=n;i++)if(!mch[i])sign++,ans+=dfs(i);
	int tot=0;
	memset(a,-1,sizeof(a));
	for(int i=1;i<=n;i++)if(mch[i]&&a[i]==-1)a[i]=a[mch[i]]=++tot;
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++)printf("%d ",a[pos(i,j)]);
		puts("");
	}
	for(int i=1;i<=n;i++)g[i].clear(),mch[i]=vst[i]=0;
	sign=0;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--)Solve();
}

上一题

© 2025 nowcoder.com