Try   HackMD

【AtCoder】Hanjo

題目連結

時間複雜度

  • 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"; }