競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

マス目を使う問題でのちょっとした実装テク

実装テク?

H行W行のマス目があって
座標(i,j)から上下左右4方向に移動が可能な問題とかそういうやつに対応します。

二次元配列で書いてもいいんですけど添え字演算子とか書く量増える上に
方向に対して番号付けできなかったりすると面倒なときがあるので便利なテク

配列のイメージに準拠しているので
data[i][j]だとするとiの若い方が上、jの若い方が左としています。

各方向についてdefineで定義しているのは手動で初期化するときにこの定義があった方が実装ミスが少なくなるからです。

使い方(共通)

int x,y; //現在の座標
for(int d=0;d<N;d++){
 int xx=x+dir[d],yy=y+dir[d+1];
 /*xx,yyが移動後の座標になる*/
}


まず基本形
現在いるマスから上下左右4方向
回る順番はこんな感じ

- 1 -
0 - 2
- 3 -
#define N 4
#define LEFT 0 
#define UP 1
#define RIGHT 2
#define DOWN 3
const int dir[N+1]={0,-1,0,1,0};

上下左右4方向に加え真ん中込み
現在いるマスから上下左右4方向
回る順番はこんな感じ

- 2 -
1 0 3
- 4 -
#define N 5
#define NOW 0
#define LEFT 1 
#define UP 2
#define RIGHT 3
#define DOWN 4
const int dir[N+1]={0,0,-1,0,1,0};


現在いるマスの斜め4方向
マクロは方角表記
回る順番はこんな感じ

0 - 1
- - -
3 - 2
#define N 4
#define NW 0
#define NE 1
#define SE 2
#define SW 3
const int dir[N+1]={-1,-1,1,1,-1};

上下左右斜め8方向
地味に時計回りじゃないので注意(多分順番は無理)
回る順番はこんな感じ

1 2 5
0 - 3
4 7 6
#define N 8
#define WW 0
#define NW 1 
#define NN 2
#define EE 3
#define SW 4
#define NE 5
#define SE 6
#define SS 7
const int dir[N+1]={0,-1,-1,0,1,-1,1,1,0};

上下左右斜め8方向+真ん中
回る順番はこんな感じ

2 3 6
1 0 4
5 8 7
#define N 9
#define NOW 0
#define WW 1
#define NW 2 
#define NN 3
#define EE 4
#define SW 5
#define NE 6
#define SE 7
#define SS 8
const int dir[N+1]={0,0,-1,-1,0,1,-1,1,1,0};