N皇后问题

打表题目

#include <iostream>

using namespace std;

int a[] = {0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724};

int main()
{
    int n;
    while (cin >> n && n)
    {
        cout << a[n] << endl;
    }
    return 0;
}

第一种搜索顺序

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20;

int n;
int ans;
bool row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s) {
    if (s > n)
        return;

    if (y == n)
        y = 0, x ++ ;

    if (x == n) {
        if (s == n) {
            ans ++ ;
        }

        return;
    }

    dfs(x, y + 1, s);

    if (!row[x] && !col[y] && !dg[x + y] && !udg[y - x + n]) {
        row[x] = col[y] = dg[x + y] = udg[y - x + n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[y - x + n] = false;
    }
}

int main() {
    while (cin >> n && n) {

        ans = 0;

        dfs(0, 0, 0);

        cout << ans << endl;
    }

    return 0;
}

第二种搜索顺序

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20;

int n;
int ans;
bool col[N], dg[N], udg[N];

void dfs(int u) {
    if (u == n) {
        ans ++ ;
        return;
    }

    for (int i = 0; i < n; i ++ )

        if (!col[i] && !dg[u + i] && !udg[i - u + n]) {
            col[i] = dg[u + i] = udg[i - u + n] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[i - u + n] = false;
        }
}

int main() {
    while (cin >> n && n) {

        ans = 0;

        dfs(0);

        cout << ans << endl;
    }

    return 0;
}

Orders

字符串全排列

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;

char g[N];
char path[N];
bool st[N];
int n;

void dfs(int u) {
    char temp = '\0';

    if (u == n) {
        for (int i = 0; i < n; i ++ )

            cout << path[i];
        puts("");
        return;
    }

    for (int i = 0; i < n; i ++ )

        if (!st[i] && g[i] != temp) {
            st[i] = true;
            path[u] = g[i];
            temp = g[i];
            dfs(u + 1);
            st[i] = false;
        }
}

int main() {
    scanf("%s", g);

    n = strlen(g);
    sort(g, g + n);

    dfs(0);

    return 0;
}

库函数写法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;

char g[N];
int n;

int main() {
    scanf("%s", g);

    n = strlen(g);
    sort(g, g + n);

    do {
        puts(g);
    } while (next_permutation(g, g + n));

    return 0;
}

Red and Black

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30;


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

int w, h;
char g[N][N];
bool st[N][N];
int fx, fy;
int ans;

void dfs(int x, int y) {
    for (int i = 0; i < 4; i ++ ) {

        int nx = x + dx[i], ny = y + dy[i];

        if (nx >= 0 && nx < h && ny >= 0 && ny < w && !st[nx][ny] && g[nx][ny] == '.') {
            st[nx][ny] = true;
            ans ++ ;
            dfs(nx, ny);
        }
    }
}

int main() {
    while (cin >> w >> h) {
        if (w == 0 && h == 0)
            break;

        memset(st, false, sizeof st);
        ans = 0;

        for (int i = 0; i < h; i ++ )

            for (int j = 0; j < w; j ++ ) {

                cin >> g[i][j];

                if (g[i][j] == '@')
                    fx = i, fy = j;
            }

        dfs(fx, fy);

        cout << ans + 1 << endl;
    }

    return 0;
}

全排列问题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i ++ )

            printf("%5d", path[i]);
        puts("");
        return;
    }

    for (int i = 1; i <= n; i ++ )

        if (!st[i]) {
            st[i] = true;
            path[u] = i;
            dfs(u + 1);
            st[i] = false;
        }
}

int main() {
    cin >> n;

    dfs(0);

    return 0;
}

库函数写法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;

int n;
int l;
int a[N];

int main() {
    cin >> n;

    for (int i = 1; i <= n; i ++ )

        a[i] = i;

    sort(a, a + n);

    do {
        for (int i = 1; i <= n; i ++ )

            printf("%5d", a[i]);
        puts("");
    } while (next_permutation(a + 1, a + n + 1));
    return 0;
}

Catch That Cow

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

typedef pair<int, int> PII;

bool st[N];
int n, k;

int bfs(int u) {
    queue<PII> q;
    PII One, next;

    One.first = u, One.second = 0;
    st[u] = true;
    q.push(One);

    while (q.size()) {
        auto t = q.front();
        q.pop();

        if (t.first == k)
            return t.second;

        next.first = t.first + 1;

        if (next.first >= 0 && next.first < N && !st[next.first]) {
            next.second = t.second + 1;
            st[next.first] = true;
            q.push(next);
        }

        next.first = t.first - 1;

        if (next.first >= 0 && next.first < N && !st[next.first]) {
            next.second = t.second + 1;
            st[next.first] = true;
            q.push(next);
        }

        next.first = t.first * 2;

        if (next.first >= 0 && next.first < N && !st[next.first]) {
            next.second = t.second + 1;
            st[next.first] = true;
            q.push(next);
        }
    }
}

int main() {
    while (cin >> n >> k) {
        memset(st, false, sizeof st);

        cout << bfs(n) << endl;
    }

    return 0;
}

棋盘问题

第一种搜索顺序

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10;

int n, k;
int ans;
char g[N][N];
bool row[N], col[N];

void dfs(int x, int y, int s) {
    if (y == n)
        y = 0, x ++ ;

    if (x == n) {
        if (s == k) {
            ans ++ ;
        }

        return;
    }

    dfs(x, y + 1, s);

    if (!row[x] && !col[y] && g[x][y] == '#') {
        row[x] = col[y] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = false;
    }
}

int main() {
    while (cin >> n >> k) {
        if (n == -1 && k == -1)
            break;

        ans = 0;

        for (int i = 0; i < n; i ++ )

            for (int j = 0; j < n; j ++ )

                cin >> g[i][j];

        dfs(0, 0, 0);

        cout << ans << endl;
    }

    return 0;
}

第二种搜索顺序

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10;

int n, k;
int ans;
char g[N][N];
bool col[N];

void dfs(int u, int s) {
    if (u == n) {
        if (s == k) {
            ans ++ ;
        }

        return;
    }

    dfs(u + 1, s);

    for (int i = 0; i < n; i ++ ) {

        if (!col[i] && g[u][i] == '#') {
            col[i] = true;
            dfs(u + 1, s + 1);
            col[i] = false;
        }
    }
}

int main() {
    while (cin >> n >> k) {
        if (n == -1 && k == -1)
            break;

        ans = 0;

        for (int i = 0; i < n; i ++ )

            for (int j = 0; j < n; j ++ )

                cin >> g[i][j];

        dfs(0, 0);

        cout << ans << endl;
    }

    return 0;
}