傳送門

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

#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();}}

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。