机试第9章

Catch That Cow(BFS)

const int MAXN = 1e5;
int step[MAXN], vis[MAXN];

int bfs(int n, int k)
{
    queue<int> q;
    q.push(n);
    step[n] = 0;
    vis[n] = 1;
    int cur, nxt;
    while (!q.empty())
    {
        cur = q.front();
        q.pop();
        for (int i = 0; i < 3; ++i)
        {
            if (i == 0)
                nxt = cur + 1;
            else if (i == 1)
                nxt = cur - 1;
            else
                nxt = 2 * cur;
            if (nxt < 0 || nxt >= MAXN)
                continue;
            if (!vis[nxt])
            {
                q.push(nxt);
                vis[nxt] = 1;
                step[nxt] = step[cur] + 1;
            }
            if (nxt == k)
                return step[nxt];
        }
    }
    return -1;
}

A Knight’s Journey(DFS)

const int MAXN = 30;
int p, q; // 棋盘参数
bool vis[MAXN][MAXN];
int dir[8][2] = {{-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-2, 1}, {2, 1}, {-1, 2}, {1, 2}};

bool dfs(int x, int y, int step, string res)
{
    if (step == p * q)
    {
        cout << res << "\n";
        return true;
    }
    for (int i = 0; i < 8; ++i)
    {
        int nx = x + dir[i][0], ny = y + dir[i][1];
        if (nx < 0 || nx >= p || ny < 0 || ny >= q || vis[nx][ny])
            continue;
        char r = nx + '1', c = ny + 'A';
        vis[nx][ny] = 1;
        if (dfs(nx, ny, step + 1, res + c + r))
            return true;
        vis[nx][ny] = 0;
    }
    return false;
}

八皇后

int res = 0, n;
vector<int> tmp;
vector<int> vis(n + 1);

void solve(int cnt, vector<int> &vis)
{
    if (cnt == n + 1)
    {
        for (int i = 0; i < tmp.size(); ++i)
            for (int j = 0; j < tmp.size(); ++j)
                if (abs(i - j) == abs(tmp[i] - tmp[j]))
                    return;
        res++;
        return;
    }
    for (int i = 1; i <= n; ++i)
        if (!vis[i])
        {
            vis[i] = 1;
            tmp.push_back(i);
            solve(cnt + 1, vis);
            tmp.pop_back();
            vis[i] = 0;
        }
}