---

title: "dfs+数学+思维（转化）"
author: Sun-Wind
date: February 1,2022

这道题可以说也是非常有意思的数学题，并且坑点也是非常多
刚开始以为是连通块的问题，后面发现没有那么简单，因为必须要分成两个部分才行，连通块可能会分成三个部分
后面想到利用割痕来解决，以为唯一的一种分割方法都会对应一种割痕，所以把所有的顶点都抽象出来
最后问题可以转化为一个01矩阵的问题
坑点有回溯，考虑两个点不能在一条边界上的情况，遇到不能走的点要及时跳出等等

敲着敲着突然发现键盘坏了，就是连续按d和a结果他会自动按f，有点小麻
当然不得不说这个题思维还是可以，可以看作01矩阵的升级版

#include <iostream>
#include <utility>
using namespace std;
typedef long long ll;
#define fi(i, a, b) for (int i = a; i <= b; ++i)
#define fr(i, a, b) for (int i = a; i >= b; --i)
#define x first
#define y second
#define sz(x) ((int)(x).size())
#define pb push_back
using pii = pair<int, int>;
//#define DEBUG
int n, m;
bool vis[10][10];
bool v[10][10];
int ans;
int matrix[10][10];
bool check(int x, int y)
{
    if (x == 1 || x == n + 1 || y == 1 || y == m + 1)
    {
        if (!matrix[x][y])
            return true;
        else
            return false;
    }
    else
        return false;
}
void dfs(int x, int y)
{
    if (v[x][y] || matrix[x][y])
        return;
        v[x][y] = true;
    if (!vis[x][y] && check(x, y))
    {
        v[x][y] = false;
        ans++;
        return;
    }
    if (x <= n && y != 1 && y != m + 1)
        dfs(x + 1, y);
    if (y <= m && x != 1 && x != n + 1)
        dfs(x, y + 1);
    if (y - 1 >= 1 && x != 1 && x != n + 1)
        dfs(x, y - 1);
    if (x - 1 >= 1 && y != 1 && y != m + 1)
        dfs(x - 1, y);
     v[x][y] = false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    matrix[1][1] = matrix[1][m + 1] = matrix[n + 1][1] = matrix[n + 1][m + 1] = 1;
    fi(i, 1, n + 1) fi(j, 1, m + 1)
    {
        if (check(i, j))
        {
            fi(i,1,n+1) fi(j,1,m+1) v[i][j] = false;
            vis[i][j] = true;
            dfs(i, j);
        }
    }
    cout << ans << endl;
#ifdef DEBUG
    //freopen(D:\in.txt,r,stdin);
#endif
    return 0;
}