题解 P2739 【[USACO4.4]棋盘游戏Shuttle Puzzle】

· · 题解

P2739 [USACO4.4]棋盘游戏Shuttle Puzzle题解

这是一道可以练习搜索的好题，我采用的是dfs和剪枝优化。

观察样例，发现白子只往右走、黑子只往左走，那么搜索总共也就四种情况：白子挪一格、白子跳一格、黑子挪一格、黑子跳一格。（注意只能跳过一个不同颜色的棋子）

剪枝也很好想，记录最少所用的步数，如果当前步数已经比它大了，就直接返回，避免因多次递归而超时。

奉上AC代码\;通过记录

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int n,a[10005],b[10005],sum = 2147483647;
string now = " ",tar = " ";//now是当前状态，tar是目标状态
void dfs(int step,int pos)//step是已用步数，pos是空格位置
{
    if (step >= sum)//剪枝
        return ;
    if (now == tar)//更新答案
    {
        sum = step;
        for (int i = 1;i <= step;i++)
        {
            a[i] = b[i];
        }
        return ;
    }
    if (pos - 2 > 0 && now[pos - 2] == 'W' && now[pos - 1] == 'B')//白子跳一格 
    {
        b[step + 1] = pos - 2;
        now[pos - 2] = ' ';
        now[pos] = 'W';
        dfs(step + 1,pos - 2);
        b[step + 1] = 0;//回溯
        now[pos - 2] = 'W';
        now[pos] = ' ';
    }
    if (pos - 1 > 0 && now[pos - 1] == 'W')//白子挪一格 
    {
        b[step + 1] = pos - 1;
        now[pos - 1] = ' ';
        now[pos] = 'W';
        dfs(step + 1,pos - 1);
        b[step + 1] = 0;
        now[pos - 1] = 'W';
        now[pos] = ' ';
    }
    if (pos + 1 <= n * 2 + 1 && now[pos + 1] == 'B')//黑子挪一格 
    {
        b[step + 1] = pos + 1;
        now[pos + 1] = ' ';
        now[pos] = 'B';
        dfs(step + 1,pos + 1);
        b[step + 1] = 0;
        now[pos + 1] = 'B';
        now[pos] = ' ';
    }
    if (pos + 2 <= n * 2 + 1 && now[pos + 2] == 'B' && now[pos + 1] == 'W')//黑子跳一格 
    {
        b[step + 1] = pos + 2;
        now[pos + 2] = ' ';
        now[pos] = 'B';
        dfs(step + 1,pos + 2);
        b[step + 1] = 0;
        now[pos + 2] = 'B';
        now[pos] = ' ';
    }
    return ;
}

int main()
{
    cin >> n;
    for (int i = 1;i <= n;i++)//产生初始状态与目标状态
    {
        now += 'W';
        tar += 'B';
    }
    now += ' ';
    tar += ' ';
    for (int i = 1;i <= n;i++)
    {
        now += 'B';
        tar += 'W';
    }
    dfs(0,n + 1);
    for (int i = 1;i <= sum;i++)
    {
        cout << a[i] << " ";
        if (i % 20 == 0)//每行20个数
            cout << endl;
    }
    cout << endl;
    return 0;
}

点个赞再走吧！