# 【AtCoder】Hanjo

## [題目連結](https://atcoder.jp/contests/abc196/tasks/abc196_d)

## **時間複雜度**

* $O((HW)^2)$

## **解題想法**

這題的解法是去枚舉每個位置的狀態，且每一個位置都有四個狀態

1. 已經被占用
2. 可以放一個 1 x 1
3. 可以橫著放一個 1 x 2
4. 可以直的放一個 1 x 2

## **完整程式**

非常值得注意的是第 31 跟 32 行前面記得一定要加 int，要讓 `ni`, `nj` 是區域變數 ~~不然就會像我一樣被卡了半天才懂找到這個 BUG~~

/* Question : AtCoder Beginner Contest 196 - D - Hanjo */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pirq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {0, 0}, {0, 1}, {1, 0} };
const int MAXN = 16 + 50;
const int Mod = 1e9 + 7;
int h, w, a, b, ans, m[MAXN][MAXN];
bool used[MAXN][MAXN];

void dfs( int i, int j, int a, int b ){
    if( a == 0 && b == 0 ){
        ans++; 
        return;
    }
    if( a < 0 || b < 0 ) return;
    if( i > h ) return;

    // Get Next Position
    int ni = i;
    int nj = j + 1;
    if( nj > w ){
        ni++;
        nj = 1;
    }

	if( used[i][j] ){
		dfs(ni, nj, a, b);
		return;
	}

    for( int t = 0 ; t < 3 ; t++ ){
        int y = i + dir[t].f;
        int x = j + dir[t].s;
        
        if( x > w || y > h ) continue;
        if( used[y][x] == true ) continue;

        used[i][j] = true;
        used[y][x] = true;
        if( t == 0 ){
            dfs(ni, nj, a, b-1);
        }else{
            dfs(ni, nj, a-1, b);
        }
        used[i][j] = false;
        used[y][x] = false;
    }
}

signed main(){
    // opt;
    mem(used, false);
    cin >> h >> w >> a >> b;
    dfs(1, 1, a, b);
    cout << ans << "\n";
}