P1706 全排列问题（dfs+递归）+P1219 [USACO1.5] 八皇后

目录

1. x表示层数，第一层选了1执行for1，进入第二层选2并标记2，第二层只进行到for2，进入第三层选3并标记3，选完之后删除标记释放3。到现在完成第一组123

2.之后回到第二层for2结束释放2再进行for3,第二层选择3，第三层从for1开始执行到for2选择2再释放2，完成第二组132

3.回到第一层执行for2,然后选2.。。。变成213,231

2.往复执行直到进行完所有全排列

2.八皇后

1. x表示层数，第一层选了1执行for1，进入第二层选2并标记2，第二层只进行到for2，进入第三层选3并标记3，选完之后删除标记释放3。到现在完成第一组123

2.之后回到第二层for2结束释放2再进行for3,第二层选择3，第三层从for1开始执行到for2选择2再释放2，完成第二组132

3.回到第一层执行for2,然后选2.。。。变成213,231

2.往复执行直到进行完所有全排列

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long int
int n,vis[20],a[20];
void pr() {
    for (int i = 1; i <= n; i++) {
        cout << setw(5) << a[i];
    }
    cout << endl;
}
void dfs(int x) {
    if (x > n) {
        pr();
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            a[x] = i;
            vis[i] = 1;
            dfs(x + 1);
            vis[i] = 0;
        }
    }
}
signed main() {
    cin >> n;
    dfs(1);
    return 0;
}

2.八皇后

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long int
int n,cnt=0;
int lie[20];
int a[20];
int zheng[30], ni[30];//从上到下的斜对角线，和从下到上的斜对角线
void pr() {
    if (cnt <= 3) {
        for (int i = 1; i <= n; i++) {
            cout << a[i]<<' ';
        }
        cout << endl;
    }
}
void dfs(int x) {
    if (x > n) {
        cnt++;
        pr();
    }
    for (int i = 1; i <= n; i++) {
        if (!lie[i]&&!zheng[x-i+n]&&!ni[x+i]) {
            lie[i] = 1;
            zheng[x-i+n] = 1;
            ni[x+i] = 1;
            a[x] = i;
            dfs(x + 1);
            lie[i] = 0;
            zheng[x-i+n] = 0;
            ni[x+i] = 0;
        }
    }
}
signed main() {
    cin >> n;
    dfs(1);
    cout << cnt;
    return 0;
}

3.P1605 迷宫(10分MLE)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long int
int xx[] = { 1,0,-1,0 };
int yy[] = { 0,-1,0,1 };
int n, m, t, sx, sy, fx, fy;
int vis[20][20];
int mp[20][20];
int ans = 0;
void dfs(int x,int y) {
    if (x==fx&&y==fy ){
        ans++;
        return;
    }
    //不断遍历上下左右四个方向，模版
    for (int i =0 ; i < 4; i++) {
        int dx = xx[i] + x;
        int dy = yy[i] + y;
        if (dx <= n && dy <= m && !vis[dx][dy] && !mp[dx][dy]) {
            vis[dx][dy] == 1;
            dfs(dx, dy);
            vis[dx][dy] == 0;
        }
    }
}
signed main() {
    cin >> n >> m >> t >> sx >> sy >> fx >> fy;
    while (t--) {
        int x, y;
        cin >> x >> y;
        mp[x][y] = 1;
    }
    vis[sx][sy] == 1;
    dfs(sx,sy);
    cout << ans;
    return 0;
}