TopCoder SRM 734 Div2 Hard TheRectangularCityDiv2

これはちょっと…。
https://community.topcoder.com/stat?c=problem_statement&pm=14902

問題

H*Wの次元グリッドが与えられる。
一部のマスは埋まっている。

周縁部のどこかの空きマスを始め、隣接マスを順にたどり、各空きマスを１回ずつ辿って最後周縁部のマスで止まるような移動順は何通りあるか。

解法

H*Wの上限が20と小さいので、移動履歴の有無をbitmaskで持ち、あと現在位置を加えて状態を持てばO(HW*2^(HW))で計算できる。

ll dp[1<<20][20];

class TheRectangularCityDiv2 {
public:
long long find(vector city) {
int H=city.size();
int W=city[0].size();
ZERO(dp);
int mask=0;
int y,x;
FOR(y,H) FOR(x,W) if(city[y][x]=='#') mask |= 1<<(y*W+x);
FOR(y,H) FOR(x,W) if(city[y][x]=='.' && (y==0 || y==H-1 || x==0 || x==W-1)) dp[mask | (1<<(y*W+x))][y*W+x]=1;

FOR(mask,1<<(H*W)) {
FOR(y,H) FOR(x,W) if(dp[mask][y*W+x]) {
if(y&&(mask&(1<<*1][(y-1)*W+x] += dp[mask][y*W+x];
if(y*2][(y+1)*W+x] += dp[mask][y*W+x];
if(x&&(mask&(1<<(y*W+x-1)))==0) dp[mask | (1<<(y*W+x-1))][y*W+x-1] += dp[mask][y*W+x];
if(x

まとめ

これは悩みどころがないし、Div2 Hardとしても安易すぎでは…。

*1:y-1)*W+x)))==0) dp[mask | (1<<((y-1)*W+x

*2:y+1)*W+x)))==0) dp[mask | (1<<((y+1)*W+x