hdu 1401/poj 1198 Solitaire(BFS，剪枝)-CSDN博客

本文链接：https://blog.csdn.net/acm_cxq/article/details/52152692

这是一篇关于ACM竞赛中的题目HDU 1401/Poj 1198 - Solitaire的解析。问题描述了一个棋盘游戏，玩家每次可以向上下左右移动，遇到棋子可以跳过但不能连续跳过两个。目标是通过广度优先搜索（BFS）找到解决方案，并应用关键的剪枝策略：如果当前步数加上未归位棋子数量大于8，则不再考虑这条路径，以减少搜索空间。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Solitaire

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4273 Accepted Submission(s): 1297

Problem Description

Solitaire is a game played on a chessboard 8x8. The rows and columns of the chessboard are numbered from 1 to 8, from the top to the bottom and from left to right respectively.

There are four identical pieces on the board. In one move it is allowed to:

> move a piece to an empty neighboring field (up, down, left or right),

> jump over one neighboring piece to an empty field (up, down, left or right).

There are 4 moves allowed for each piece in the configuration shown above. As an example let's consider a piece placed in the row 4, column 4. It can be moved one row up, two rows down, one column left or two columns right.

Write a program that:

> reads two chessboard configurations from the standard input,

> verifies whether the second one is reachable from the first one in at most 8 moves,

> writes the result to the standard output.

Input

Each of two input lines contains 8 integers a1, a2, ..., a8 separated by single spaces and describes one configuration of pieces on the chessboard. Integers a2j-1 and a2j (1 <= j <= 4) describe the position of one piece - the row number and the column number respectively. Process to the end of file.

Output

The output should contain one word for each test case - YES if a configuration described in the second input line is reachable from the configuration described in the first input line in at most 8 moves, or one word NO otherwise.

Sample Input

  
  
   
   4 4 4 5 5 4 6 5
2 4 3 3 3 6 4 6

Sample Output

YES

题意：给你8*8棋盘上四个棋子的起始坐标和终点坐标，问能否在八步之内（包含八步）之内走到

每一步可以向上下左右走，如果有一个棋子挡着可以跳过这个棋子，两个棋子就不行了。

最终状态的四个棋子不用按照起始状态的四个棋子的顺子，只要能达到这个状态就可以了。

思路：单向广搜即可，不过需要一步至关重要的剪枝。我们知道让一个棋子归位至少要一步，所以如果当前步数+未归位棋子数量>8就不要入队即可

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
struct Node
{
    int x[4],y[4];
    int step;
    int need;
} b;
bool vis[8][8][8][8][8][8][8][8];
int ma[10][10];
int dir[4][2]= {-1,0,1,0,0,-1,0,1};
queue<Node>que;
int check(Node a,int x,int y,int x1,int y1)
{
    int flag=0;
    if(x<1||x>8||y<1||y>8) return 0;
    for(int i=0; i<4; i++)
        if(a.x[i]==x&&a.y[i]==y)
        {
            flag=1;
            if(x1<1||x1>8||y1<1||y1>8)
                return 0;
            for(int j=0; j<4; j++)
                if(a.x[j]==x1&&a.y[j]==y1)
                    return 0;
            break;
        }
    if(flag) return 2;
    return 1;
}
int judge(Node a)
{
    for(int i=0; i<4; i++)
        if(!ma[a.x[i]][a.y[i]])
            return 0;
    return 1;
}
void bfs(Node a)
{
    Node next;
    a.step=0;
    a.need=4;
    for(int i=0;i<4;i++)
        if(ma[a.x[i]][a.y[i]])
            a.need--;
    while(!que.empty())
        que.pop();
    que.push(a);
    memset(vis,false,sizeof(vis));
    vis[a.x[0]-1][a.y[0]-1][a.x[1]-1][a.y[1]-1][a.x[2]-1][a.y[2]-1][a.x[3]-1][a.y[3]-1]=true;
    while(!que.empty())
    {
        Node now=que.front();
        que.pop();
        if(now.step>8)
        {
            printf("NO\n");
            return;
        }
        if(judge(now))
        {
            printf("YES\n");
            return;
        }
        if(now.step==8)
            continue;
        for(int i=0; i<4; i++)
        {
            for(int j=0; j<4; j++)
            {
                next=now;
                next.x[j]=now.x[j]+dir[i][0],next.y[j]=now.y[j]+dir[i][1];
                int tx=next.x[j]+dir[i][0],ty=next.y[j]+dir[i][1];
                int flag=check(now,next.x[j],next.y[j],tx,ty);
                if(!flag) continue;
                else if(flag==2) next.x[j]=tx,next.y[j]=ty;
                if(vis[next.x[0]-1][next.y[0]-1][next.x[1]-1][next.y[1]-1][next.x[2]-1][next.y[2]-1][next.x[3]-1][next.y[3]-1]) continue;
                vis[next.x[0]-1][next.y[0]-1][next.x[1]-1][next.y[1]-1][next.x[2]-1][next.y[2]-1][next.x[3]-1][next.y[3]-1]=true;
                if(judge(next))
                {
                    printf("YES\n");
                    return;
                }
                next.step=now.step+1;
                next.need-=ma[next.x[j]][next.y[j]]-ma[now.x[j]][now.y[j]];
                if(next.need+next.step>8) continue;
                que.push(next);
            }
        }
    }
    printf("NO\n");
}
int main()
{
    Node a;
    while(~scanf("%d %d %d %d %d %d %d %d",&a.x[0],&a.y[0],&a.x[1],&a.y[1],&a.x[2],&a.y[2],&a.x[3],&a.y[3]))
    {
        scanf("%d %d %d %d %d %d %d %d",&b.x[0],&b.y[0],&b.x[1],&b.y[1],&b.x[2],&b.y[2],&b.x[3],&b.y[3]);
        memset(ma,0,sizeof(ma));
        ma[b.x[0]][b.y[0]]=1;
        ma[b.x[1]][b.y[1]]=1;
        ma[b.x[2]][b.y[2]]=1;
        ma[b.x[3]][b.y[3]]=1;
        bfs(a);
    }
    return 0;
}