Submission #92491

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cassert>
using namespace std;
typedef long long ll;

#define REP(i,n) for (int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define FOREQ(i,k,n) for (int i=(k); i<=(int)(n); ++i)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ(v) (int)((v).size())
#define MEMSET(v,h) memset((v),(h),sizeof(v))


int ret = 0;
int w, h;
int f[40][40];
void dfs(int y, int x) {
  if (x==w) { dfs(y+1,0); return; }
  if (y==h) { ret++; return; }

  FOREQ(t, 1, 3) {
    f[y][x]=t;

    FOREQ(k, max(0, y-t), y-1) if (f[k][x] == t) goto SKIP;
    FOREQ(k, max(0, x-t), x-1) if (f[y][k] == t) goto SKIP;
    dfs(y, x+1);
SKIP:;
  }
}

int got(int W, int H) {
  if (W<=10 && H<=10) {
    w=W, h=H;
    ret=0;
    dfs(0,0);
    return ret;
  }
  if (W==1) swap(W, H);
  if (H==1) {
    if (W%4==0) return 10;
    if (W%4==1) return 9 ;
    if (W%4==2) return 8 ;
    if (W%4==3) return 9 ;
  }

  if ((W+H)%2==0) return 18;
  if ((W+H)%4==1) return 20;
  if ((W+H)%4==3) return 16;

  return -1;
}

int main() {
  /*
  FOREQ(w, 1, 30) {
    FOREQ(h, 1, 30) {
      W=w, H=h;
      ret=0;
      dfs(0,0);
      printf(" ");
      if (ret<10) printf(" ");
      printf("%d", ret);
    }
    cout<<endl;
  }
  */
  int W,H;
  cin >> W >> H;
  cout << got(W, H) << endl; 


}

Submission Info

Judge Result