本文主要是介绍AtCoder Beginner Contest 196 D Hanjo （dfs + 状压），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
今天第一次学到给二维数组编号然后用二进制标记状态…
别人这dfs用的是真6啊
二进制状压：设这个数组的大小为n * m 那么 a[i][j] 对应的编号可以表示为(i-1) * m + j, 对应到二进制如果编号为i，如果bit & 1 << i为1表示该位置已经被使用过了。同理要想标记第i个位置：bit | 1 << i;
对应到这题因为数据很小我们可以直接遍历每一种情况，注意长方形有两种摆法。
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
typedef pair<int, int> P;const int maxn = 1e5 + 10;
const int M_MAX = 50000 + 10;
const int mod = 1e9 + 7;
const LL INF = 1e17;
const double eps = 1e-6; int H, W, A, B, ans;void dfs(int i, int bit, int a, int b) {if(i == H * W) return (void) ans++;if(bit & 1 << i) return dfs(i+1, bit, a, b);if(b) dfs(i + 1, bit | 1 << i, a, b - 1);if(a) {if(i % W != W - 1 && ~bit | 1 << i+1) dfs(i+1,bit | 1 << i | 1 << i + 1, a - 1, b);if(i + W < H * W) dfs(i+1, bit | 1 << i | 1 << i + W, a - 1, b); }
}void solve() {cin >> H >> W >> A >> B;dfs(0, 0, A, B);cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);//freopen("D:\\in.txt", "r", stdin);solve();return 0;
}
这篇关于AtCoder Beginner Contest 196 D Hanjo （dfs + 状压）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
