リハビリ(^−^)
あー全然パソコン触れなくて悲しみ...
校内模試とはなんだったのでしょうか
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; }