リハビリ（＾−＾）

あー全然パソコン触れなくて悲しみ...
校内模試とはなんだったのでしょうか

PKU 3254(3254 -- Corn Fields)
bitdpすると解けます

#include <cstdio>
#include <cstring>
using namespace std;
#define mod 100000000

int m, n;
int map[13][13];
int dp[1 << 12][12][12];

int solve(int bit, int pos){
    int x = pos % n, y = pos / n;
    if(x == 0 && y == m) return 1;
    int res = 0;
    if(dp[bit][x][y] >= 0) return dp[bit][x][y];
    if(map[x][y] == 0) res = solve((bit << 1) & ((1 << n) - 1), pos + 1);
    else{
	int crt = bit;
	res = solve((crt << 1) & ((1 << n) - 1), pos + 1);
	if(!(crt & (1 << (n - 1)) || ((x != 0) && (crt & 1)))){
	    crt = ((bit << 1) & ((1 << n) - 1)) | 1;
	    res += solve(crt, pos + 1);
	}
	res %= mod;
    }
    dp[bit][x][y] = res;
    return res;
}

int main(){
    scanf("%d %d", &m, &n);
    for(int i = 0; i < m; i++){
	for(int j = 0; j < n; j++){
	    scanf("%d", &map[j][i]);
	}
    }
    memset(dp, -1, sizeof(dp));
    printf("%d\n", solve(0,0));
    return 0;
}