## 50

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, k;
int ans;
bool vis[10][10];
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[] = {1, -1, 0, 0, 1, 1, -1, -1};
void dfs(int x, int y, int cnt)
{
    if (y == n + 1)
    {
        x++;
        y = 1;
    }
    if (cnt == k)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                for (int k = 0; k < 8; k++)
                {
                    int ii = i + dx[k];
                    int jj = j + dy[k];
                    if (vis[ii][jj] && vis[i][j])
                        return;
                }
            }
        ans++;
        return;
    }
    if(x==n+1)
        return ;
    vis[x][y] = true;
    dfs(x, y + 1, cnt + 1);
    vis[x][y] = false;
    dfs(x, y + 1, cnt);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    ans = 0;
    dfs(1, 1, 0);
    cout << ans;
    return 0;
}
```

## 70

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, k;
int ans;
bool vis[10][10];
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[] = {1, -1, 0, 0, 1, 1, -1, -1};
void dfs(int x, int y, int cnt)
{
    if (y == n + 1)
    {
        x++;
        y = 1;
    }
    if (cnt == k)
    {
        ans++;
        return;
    }
    if (x == n + 1)
        return;
    if (!vis[x - 1][y - 1] && !vis[x - 1][y] &&
        !vis[x - 1][y + 1] && !vis[x][y - 1])
    {
        vis[x][y] = true;
        dfs(x, y + 1, cnt + 1);
    }
    vis[x][y] = false;
    dfs(x, y + 1, cnt);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    ans = 0;
    dfs(1, 1, 0);
    cout << ans;
    return 0;
}
```

## 70 

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, k;
int ans;
int vis[11][11];
int dx[] = {0, 1, 1, 1};
int dy[] = {1, -1, 0, 1};
void dfs(int x, int y, int cnt)
{
    if (y == n + 1)
    {
        x++;
        y = 1;
    }
    if (cnt == k)
    {
        ans++;
        return;
    }
    if (x == n + 1)
        return;
    if (vis[x][y] == 0)
    {
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            vis[xx][yy]++;
        }
        dfs(x, y + 1, cnt + 1);
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            vis[xx][yy]--;
        }
    }
    if (cnt + (n - x) * n + (n - y) >= k)
    {
        dfs(x, y + 1, cnt);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    ans = 0;
    dfs(1, 1, 0);
    cout << ans;
    return 0;
}
```

## 100

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k, ans;
vector<int> ok;   // 存所有合法状态
vector<int> cnt1; // ok[i] 一共有 cnt1[i] 个 1
int dp[10][90][1 << 9];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    // 预处理所有单行的合法状态
    for (int i = 0; i <= (1 << n) - 1; i++)
        if (!(i & (i >> 1)))
        {
            ok.push_back(i);
            int temp = 0;
            for (int j = 0; j <= n - 1; j++)
                if (i & (1 << j))
                    temp++;
            cnt1.push_back(temp);
        }
    // dp
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= min(k, n * i); j++)
            for (int k = 0; k < ok.size(); k++)
            {
                int sta = ok[k];
                int cnt = cnt1[k];
                if (cnt > j)
                    continue;
                for (int pre : ok)
                {
                    if ((sta & pre) ||
                        (sta & (pre << 1)) ||
                        (sta & (pre >> 1)))
                        continue;
                    dp[i][j][sta] += 
                        dp[i - 1][j - cnt][pre];
                }
            }
    // ans
    ans = 0;
    for (int sta : ok)
        ans += dp[n][k][sta];
    cout << ans;
    return 0;
}
```