AOJ 1007: JPEG Compression
問題
JPEG Compression | Aizu Online Judge
NxNのマスをジグザグに走査するとき、各マスにアクセスする順番を求めよ
方針
- 合計
sum
になる(y,x)
の組ごとに考える sum
が偶数なら右上に、奇数なら左下に進んでいく- 次に進むマスが範囲外なら
sum
の偶奇とn
との関係に気をつけてsum+1
における最初のマスに移動する
コード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(n); ++i) int a[10][10]; int main(void){ int n, c=1; while(cin >> n && n) { int idx = 1; int x = 1; int y = 0; int d = 1; a[0][0] = 1; for(int sum = 1; sum <= 2*n-2; ++sum) { for(;;) { a[y][x] = ++idx; if(y==n-1 && x==n-1) break; if(sum%2==0) {x++; y--;} else {x--; y++;} if(x < 0 || y < 0 || x >= n || y >= n) break; } if(sum < n-1) { if(sum%2==1) {x=0; y=sum+1;} else {y=0; x=sum+1;} } else { if(sum%2==1) {y=n-1; x=sum+1-y;} else {x=n-1; y=sum+1-x;} } } printf("Case %d:\n", c); rep(i, n) { rep(j, n) { if(a[i][j]>=100) cout << a[i][j]; else if(a[i][j]>=10) cout << " " << a[i][j]; else cout << " " << a[i][j]; } cout << endl; } c++; } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1901570
反省
- 意外とジグザグの処理に手間取った
- すごいコードはすごい(分かりやすいのだとhttp://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=187849#1)