网站建设找扌金手指排名,一流的网站建设与优化,wordpress 调用GPS,电脑系统下载官方网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个n∗mn*mn∗m的矩形#xff0c;包含...和XXX#xff0c;你有两种颜色#xff0c;你需要给...染色使得每个XXX上下左右相邻的...其两种颜色个数相同#xff0c;输出一种合法方案。 1≤n,m≤5001\l…传送门 文章目录题意思路题意
给你一个n∗mn*mn∗m的矩形包含...和XXX你有两种颜色你需要给...染色使得每个XXX上下左右相邻的...其两种颜色个数相同输出一种合法方案。
1≤n,m≤5001\le n,m\le 5001≤n,m≤500
思路
考虑XXX周围...的个数的情况。
(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)连边(x1,y)(x,y1)(x1,y)(x,y1)(x1,y)(x,y1)连边让后跑二分图染色即可。
对于(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,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#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 pairint,int PII;const int N510,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
PII a[N];
char s[N][N];
int dir[4][2]{-1,0,0,-1,1,0,0,1};
vectorintv[N*N*2];
int col[N*N],flag;int id(int x,int y) {return (x-1)*my;
}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) flag1;}
}bool check() {for(int i1;in;i) {for(int j1;jm;j) {if(s[i][j]!X) continue;int cnt0;for(int k0;k4;k) {int dxidir[k][0];int dyjdir[k][1];if(dx1||dy1||dxn||dym) continue;cnts[dx][dy].;if(s[dx][dy].) a[cnt]{dx,dy};}if(cnt%2) return false;if(cnt2) {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));}}}flag0;for(int i1;in*m;i) col[i]0;for(int i1;in*m;i) if(s[(i-1)/m1][(i-1)%m1]!X!col[i]!flag) dfs(i,1); if(flag) return false;puts(YES);for(int i1;in;i) {for(int j1;jm;j) {int valid(i,j);if(s[i][j]X) {int cnt0;for(int k0;k4;k) {int dxidir[k][0];int dyjdir[k][1];if(dx1||dy1||dxn||dym) continue;cnts[dx][dy].;if(s[dx][dy].) a[cnt]{dx,dy};}if(cnt0) printf(0 );else if(cnt2) 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 i1;in;i) scanf(%s,s[i]1);if(!check()) puts(NO);int x;return 0;
}
/**/
