ARC080 D : Grid Coloring(400)
作成日：2017.08.07
最終更新日：2017.08.07
問題概要
縦$H$行、横$W$行のマス目を$N$色で塗り分ける。
$i$色目で塗られたマスが$a_i$個あり、それらが上下左右に隣り合っているような塗り方を求めよ。
制約
$1 \leq H,W \leq 100$
$1 \leq N \leq HW$
$a_i \geq 1$
$\sum_{1 \leq i \leq N}{a_i} = HW$
考え方
$H=1$の時は$i$色目で$a_i$個連続でマスを塗るということを繰り返せば良い。
そうでない時、まず$H=1$の時と同様に一列に並んだマスに色を塗ってから$H$行にすることを考える。
これはひもを平面に敷き詰めることと同じであるから、渦巻き状やジグザグに並べれば良い。
実装の容易さを考えてジグザグに並べることにする。
ソースコード
マクロ等はこちら
int H,W,N;
int ans[111][111];
int p;
int main(){
scanf("%d%d%d" , &H , &W , &N);
repp(i,1,N+1){
int a;
scanf("%d" , &a);
while(a > 0){
ans[p/W][(p/W)%2==1?W-1-(p%W):(p%W)] = i;
++p;
--a;
}
}
repp(i,0,H){
repp(j,0,W){
printf("%d%c" , ans[i][j] , j+1==W ? '\n' : ' ');
}
}
return 0;
}解法まとめ
各色$a_i$個連続にすでに塗り終わったマスに続いてジグザグに塗っていく。(7-15行)