地址:http://arc080.contest.atcoder.jp/tasks/arc080_b
题目:
D - Grid Coloring
Time limit : 2sec / Memory limit : 256MB
Score : 400 points
Problem Statement
We have a grid with H rows and W columns of squares. Snuke is painting these squares in colors 1, 2, …, N. Here, the following conditions should be satisfied:
- For each i (1≤i≤N), there are exactly ai squares painted in Color i. Here, a1+a2+…+aN=HW.
- For each i (1≤i≤N), the squares painted in Color i are 4-connected. That is, every square painted in Color i can be reached from every square painted in Color i by repeatedly traveling to a horizontally or vertically adjacent square painted in Color i.
Find a way to paint the squares so that the conditions are satisfied. It can be shown that a solution always exists.
Constraints
- 1≤H,W≤100
- 1≤N≤HW
- ai≥1
- a1+a2+…+aN=HW
Input
Input is given from Standard Input in the following format:
H W
N
a1 a2 … aN
Output
Print one way to paint the squares that satisfies the conditions. Output in the following format:
c11 … c1W
:
cH1 … cHW
Here, cij is the color of the square at the i-th row from the top and j-th column from the left.
思路:蛇形填数即可
#include <bits/stdc++.h> using namespace std; #define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-;
const double pi=acos(-1.0);
const int K=1e6+;
const int mod=1e9+; int r,c,n,x,y,ans[][]; int main(void)
{
scanf("%d%d%d",&r,&c,&n);
x=,y=;
for(int i=,cnt;i<=n;i++)
{
scanf("%d",&cnt);
while(cnt--)
{
ans[x][y]=i;
if(y==c&&x%==)
y=c,x++;
else if(y==&&x%==)
y=,x++;
else if(x&)
y++;
else
y--;
}
}
for(int i=;i<=r;i++)
for(int j=;j<=c;j++)
printf("%d%c",ans[i][j],j==c?'\n':' ');
return ;
}