Code-Festival-2017-qualA_____D - Four Coloring

AtCoder

---

题目：

输入 $H \ W \ D$
输出矩阵的最终颜色

Solution:

这里的关键是曼哈顿距离的矩阵旋转 $\Large{\frac{\pi}{2}}$ 后再将距离乘 $\sqrt{2}$ 就得到了一个新的矩阵，其点与点之间的距离为切比雪夫距离

Proof:

点 $(x,y)$ 绕 $(0,0)$ 旋转 $\alpha$ 后得到点 $(x',y')$
设点 $(x,y)$ 原先的极角为 $\theta$
由：

$$\frac{x}{cos \theta}=\frac{x'}{cos(\theta - \alpha)}$$

$$\frac{y}{sin \theta}=\frac{y'}{sin(\theta - \alpha)}$$

得：

$$x'=xcos(\alpha)+ysin(\alpha)$$

$$y'=ycos(\alpha)-xsin(\alpha)$$

当 $\alpha$ 为 $\Large{\frac{\pi}{2}}$ 时 结果显然

---

我的代码里 $ans[\ ][\ ]$ 直接表示一个点的坐标处放的颜色,而不直接是答案

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 1009;
int n,m,d;
int mat[MAXN][MAXN];
int ans[MAXN][MAXN];
int ADD;
int cal(int x,int y){
    if(x%2==1){
        if(y%2==1)
            return 1;
        else
            return 2;
    }
    else{
        if(y%2==1)
            return 3;
        else
            return 4;
    }
}
int locx(int x,int y){
    if((x+y-1)%d==0){
        return (x+y-1)/d;
    }
    else
        return (x+y-1)/d+1;
}
int locy(int x,int y){
    if((y-x+m)%d==0)
        return (y-x+m)/d;
    else
        return (y-x+m)/d+1;
}
void COLOR(){
    int i,j;
    for(i=1;i<=(n+m)/d+1;i++){
        for(j=1;j<=(n+m)/d+1;j++){
            mat[i][j]=cal(i,j);
        }
    }
}
void REMAP(){
    int i,j;
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            ans[i][j]=mat[locx(i,j)][locy(i,j)];
        }
    }
}
char GETCHAR(int x){
    if(x==1)return 'R';
    if(x==2)return 'G';
    if(x==3)return 'Y';
    if(x==4)return 'B';
}
void OUT(){
    int i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            printf("%c",GETCHAR(ans[j][i]));
        }
        puts("");
    }
}
void solve(){
    COLOR();
    REMAP();
    OUT();
}
int main(){
    scanf("%d%d%d",&n,&m,&d);
    solve();
    return 0;
}