AOJ 0203 - A New Plan of Aizu Ski Report

memo[y][x]: 座標(y, x)からはじめたときに滑れるパターンの総数
(座標は(0, 0)を始点とする)

w*hのコースでの滑り終わりは(x, h-1)

(1)の!(map[y+1][x+i] == 2 && i != 0)は
A: 元のx座標と次に行くx座標が同じ
B: 次のところにはジャンプ台があるとして，
カルノー図を書くと，

	¬A	A
¬B	1
B	1	1

これは¬(A∧¬B)であることを利用している．

#include<iostream>

int w, h;
int map[16][15], memo[16][15];

int rec(int x, int y){
	if(memo[y][x] >= 0){
		return memo[y][x];
	}

	if(map[y][x] == 1){
		return 0;
	}

	if(y >= h-1){
		return 1;
	}

	int res = 0;
	if(map[y][x] == 0){
		for(int i=-1;i<2;i++){
			if(x+i >= 0 && x+i < w && !(map[y+1][x+i] == 2 && i != 0)){//(1)
				res += rec(x+i, y+1);
			}
		}
		return memo[y][x] = res;
	}else if(map[y][x] == 2){
		return memo[y][x] = rec(x, y+2);
	}
}

int main(){
	while(std::cin >> w >> h, w){

		for(int i=0;i<16;i++){
			for(int j=0;j<15;j++){
				memo[i][j] = -1;
				map[i][j] = 0;
			}
		}

		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				std::cin >> map[i][j];
			}
		}

		int res = 0;
		for(int i=0;i<w;i++){
			res += rec(i, 0);
		}

		std::cout << res << std::endl;
	}
}