IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> Codeforces Round #742 (Div. 2) F. One-Four Overload 构造 + 二分图染色 -> 正文阅读

[数据结构与算法]Codeforces Round #742 (Div. 2) F. One-Four Overload 构造 + 二分图染色

传送门

文章目录

题意:

给你一个 n ? m n*m n?m的矩形,包含 . . . X X X,你有两种颜色,你需要给 . . .染色使得每个 X X X上下左右相邻的 . . .其两种颜色个数相同,输出一种合法方案。

1 ≤ n , m ≤ 500 1\le n,m\le 500 1n,m500

思路:

考虑 X X X周围 . . .的个数的情况。

( 1 ) (1) (1) 当有奇数个 . . .的时候,显然不可能有合法解。

( 2 ) (2) (2)当有两个 . . .的时候,我们将其连边,变成一个图,显然可以直接二分图染色构造答案。

( 3 ) (3) (3)当有四个 . . .的时候,这个就比较麻烦了,一种可行方案就是 ( x ? 1 , y ) < = > ( x , y ? 1 ) (x-1,y)<=>(x,y-1) (x?1,y)<=>(x,y?1)连边, ( x + 1 , y ) < = > ( x , y + 1 ) (x+1,y)<=>(x,y+1) (x+1,y)<=>(x,y+1)连边,让后跑二分图染色即可。

对于 ( 3 ) (3) (3)的正确性官方题解有说,其实并没怎么看懂,但是自己画一下应该可以发现这样是可以的,因为要是出来奇数环的话需要奇数条边,而这种斜边必须是偶数个,那么横边必须是奇数个,貌似可以感性认知一下?雀氏不是很会证。

// Problem: F. One-Four Overload
// Contest: Codeforces - Codeforces Round #742 (Div. 2)
// URL: https://codeforces.com/contest/1567/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std;

//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }
//void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }
//void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

const int N=510,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;

int n,m;
PII a[N];
char s[N][N];
int dir[4][2]={-1,0,0,-1,1,0,0,1};
vector<int>v[N*N*2];
int col[N*N],flag;

int id(int x,int y) {
	return (x-1)*m+y;
}

void dfs(int u,int color) {
	if(flag) return;
	col[u]=color;
	for(auto x:v[u]) {
		if(flag) break;
		if(!col[x]) dfs(x,3-color);
		else if(col[x]==color) flag=1;
	}
}

bool check() {
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			if(s[i][j]!='X') continue;
			int cnt=0;
			for(int k=0;k<4;k++) {
				int dx=i+dir[k][0];
				int dy=j+dir[k][1];
				if(dx<1||dy<1||dx>n||dy>m) continue;
				cnt+=s[dx][dy]=='.';
				if(s[dx][dy]=='.') a[cnt]={dx,dy};
			}
			if(cnt%2) return false;
			if(cnt==2) {
				v[id(a[1].X,a[1].Y)].pb(id(a[2].X,a[2].Y));
				v[id(a[2].X,a[2].Y)].pb(id(a[1].X,a[1].Y));
			} else {
				v[id(a[1].X,a[1].Y)].pb(id(a[2].X,a[2].Y));
				v[id(a[2].X,a[2].Y)].pb(id(a[1].X,a[1].Y));
				v[id(a[3].X,a[3].Y)].pb(id(a[4].X,a[4].Y));
				v[id(a[4].X,a[4].Y)].pb(id(a[3].X,a[3].Y));
			}
		}
	}
	flag=0;
	for(int i=1;i<=n*m;i++) col[i]=0;
	for(int i=1;i<=n*m;i++) if(s[(i-1)/m+1][(i-1)%m+1]!='X'&&!col[i]&&!flag) dfs(i,1); 
	if(flag) return false;
	puts("YES");
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			int val=id(i,j);
			if(s[i][j]=='X') {
				int cnt=0;
				for(int k=0;k<4;k++) {
					int dx=i+dir[k][0];
					int dy=j+dir[k][1];
					if(dx<1||dy<1||dx>n||dy>m) continue;
					cnt+=s[dx][dy]=='.';
					if(s[dx][dy]=='.') a[cnt]={dx,dy};
				}
				if(cnt==0) printf("0 ");
				else if(cnt==2) printf("5 ");
				else printf("10 ");
			}
			else if(col[val]==1) printf("1 ");
			else printf("4 ");
		}
		puts("");
	}
	return true;
}

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);	

	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	if(!check()) puts("NO");

int x;


	return 0;
}
/*

*/









  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-09-24 10:50:25  更:2021-09-24 10:53:45 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 4:52:01-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码