Submission #92220

---

Source Code Expand

// include {{{
#include <cstdio>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
//#include <deque>
#include <stack>
#include <queue>
//#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <numeric>
//#include <complex>
// }}}
using namespace std;
// macro {{{
typedef long long ll;
typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0,__end=(n);i<__end;++i)
#define REP(i,j,k) for(int i=j,__end=(k);i<__end;++i)
//#define foreach(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();++it)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define priority_queue_greater(T) priority_queue< T, vector<T>, greater<T> >
#define F first
#define S second
// BEGIN CUT HERE {{{
// convert {{{
template<typename T> T fromString(string& s){
  T res;
  std::istringstream is(s);
  is >> res;
  return res;
}
template<typename T> string toString(T& v){
  stringstream ss;
  ss << v;
  return ss.str();
} // }}}
// inspect {{{
string inspect( string str );
template<typename T> string inspect( T v );
template<typename T,typename U> string inspect( pair<T,U> v );
template<typename T> string inspect( vector<T> v );
string inspect( string str ){
  return "\"" + str + "\"";
}
template<typename T> string inspect( T v ){
  return toString<T>( v );
}
template<typename T,typename U> string inspect( pair<T,U> v ){
  return "(" + inspect(v.first) + "," + inspect(v.second) + ")";
}
template<typename T> string inspect( vector<T> v ){
  string res = "[";
  rep(i,v.size()){
    if( i != 0 ){ res += ","; }
    res += inspect( v[i] );
  }
  return res + "]";
}
// }}}
// puts {{{
template<typename T> void puts( T val ){
  cout << inspect(val) << endl;
}
template<typename T> void puts( string name, T val ){
  cout << name << ": " << inspect(val) << endl;
}
// }}}
// END CUT HERE }}}
// }}}

int w,h;

int count(int i, mat& map){
  if( w * h <= i ){ return 1; }
  int y = i / w;
  int x = i % w;
  //puts(P(x,y));

  int res = 0, now;
  bool check;
  // 1
  check = true;
  now = 1;
  if(0 < y && map[y-1][x] == now){ check = false; }
  if(0 < x && map[y][x-1] == now){ check = false; }
  if(check){
    map[y][x] = 1;
    res += count(i+1,map);
  }
  // 2
  check = true;
  now = 2;
  if(0 < y && map[y-1][x] == now){ check = false; }
  if(0 < x && map[y][x-1] == now){ check = false; }
  if(1 < y && map[y-2][x] == now){ check = false; }
  if(1 < x && map[y][x-2] == now){ check = false; }
  if(check){
    map[y][x] = 2;
    res += count(i+1,map);
  }
  // 3
  check = true;
  now = 3;
  if(0 < y && map[y-1][x] == now){ check = false; }
  if(0 < x && map[y][x-1] == now){ check = false; }
  if(1 < y && map[y-2][x] == now){ check = false; }
  if(1 < x && map[y][x-2] == now){ check = false; }
  if(2 < y && map[y-3][x] == now){ check = false; }
  if(2 < x && map[y][x-3] == now){ check = false; }
  if(check){
    map[y][x] = 3;
    res += count(i+1,map);
  }

  map[y][x] = 0;
  return res;
}

int main(){
  while( cin >> w >> h ){
    if( w > 4 || h > 4 ){ cout << 42 << endl; continue; }
    mat map(h, vec(w,0));
    cout << count(0, map) << endl;
  }
  return 0;
}

Submission Info

Judge Result