算法提高课汇总

算法思路

最小步数模型. 对于搜索来说其核心是搜索顺序: 保证枚举所有可行方案(一般求方案数或最优解).

本题顺序: 递归每层均按8个日的顺序扩展结点, 构成一个$dfs$搜索树.

• 对于这个搜索树, 每条从根到叶子节点的路径均对应一种方案, 且不同路径之间至少有一步不同.

• 此时节点的回溯由系统栈实现.

具体实现

最小步数模型中$dfs$的时间复杂度一般为指数级.

#include <iostream>

using namespace std;

const int N = 10;

int n, m;
int ans; //全局变量记录方案数
bool st[N][N];

int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[] = {1, 2, 2, 1, -1 ,-2, -2, -1};

//(x, y): 当前节点位置; cnt: 当前已经遍历节点的数目
void dfs(int x, int y, int cnt)
{
    if ( cnt == n * m )
    {
        ans ++ ;
        return;
    }

    st[x][y] = true;
    for ( int i = 0; i < 8; i ++ )
    {
        int nx = x + dx[i], ny = y + dy[i];
        if ( nx < 0 || nx >= n || ny < 0 || ny >= m )   continue;
        if ( st[nx][ny] )   continue;

        dfs(nx, ny, cnt + 1);
    }
    st[x][y] = false;
}

int main()
{
    int T;
    cin >> T;
    while ( T -- )
    {
        int x, y;
        cin >> n >> m >> x >> y;

        ans = 0;
        dfs(x, y, 1);
        cout << ans << endl;
    }
    return 0;
}