傳送門

由于曼哈頓距離在圖上顯示的是一個(gè)棱形，并不是很好看，所以我們將其旋轉(zhuǎn)$45°$，轉(zhuǎn)換成切比雪夫距離，這樣就變成了一個(gè)正方形，正方形內(nèi)部的點(diǎn)距離都不超過$d$，此時(shí)可以將正方形內(nèi)部的點(diǎn)看成一個(gè)整體，涂成一個(gè)顏色，將其縮為一個(gè)點(diǎn)，讓后現(xiàn)在問題就變成了你需要將每個(gè)點(diǎn)與其周圍8個(gè)方向的點(diǎn)的顏色都不相同，這個(gè)就是四色定理，可以按照如下方式構(gòu)造：
$$\begin{gathered} 12121212... \\ 34343434... \\ 12121212... \\ 34343434... \\ ... \end{gathered}$$
不難發(fā)現(xiàn)符合上述限制，所以我們只需要將其轉(zhuǎn)換成切比雪夫距離，讓后根據(jù)奇偶判斷一下即可。

#include<bits/stdc++.h> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define Mid (tr[u].l+tr[u].r>>1) #define pb push_back using namespace std;const int N=1000010,INF=0x3f3f3f3f,mod=1e9+7; typedef long long LL;int n,m,d;void solve() {cin>>n>>m>>d;for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {int x=(i+j+1000)/d,y=(i-j+1000)/d;//cout<<i<<' '<<j<<' '<<x<<' '<<y<<endl;//int digit=(x%2)*2+y%2;if(x%2==1) {if(y%2==1) printf("R");else printf("Y");} else {if(y%2==1) printf("G");else printf("B");}}puts("");} }int main() {int _=1;while(_--) {solve();}}

總結(jié)

以上是生活随笔為你收集整理的AT3557 Four Coloring 切比雪夫距离 + 四色构造的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。