浙江财经大学
信工学院ACM集训队

HDU 1401 Solitaire(BFS)

本文由 Ocrosoft 于 2016-07-08 11:49:29 发表

Solitaire

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

Problem Description
Solitaire is a game played on a chessboard 8×8. 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
 

Solution

题意:给出4个棋子的初始态和最终态,问8步以内能不能由初始态变成最终态。棋子可以上下左右走一格,如果走的方向有棋子,那么可以跳过这个棋子(如果跳过去后还有棋子那么不能跳)。

因为棋子有4个,每个有x和y,所以要开8维的数组记录状态。8^8比较大,一定要开成bool,开成int会占用4倍空间。因为这个MLE了无数次。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#include <climits>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
int mp[8][8];
int dir[4][2]= {1,0,-1,0,0,1,0,-1};
bool vis[8][8][8][8][8][8][8][8];
struct node
{
    int x[4],y[4];
    int step;
} sp,ep;
bool check(node p)//判断是否为最终态,1=最终态
{
    for(int i=0; i<4; i++)
        if(!mp[p.x[i]][p.y[i]])
            return 0;
    return 1;
}
bool judge(node p,int k)//判断非空,0=非空
{
    for(int i=0; i<4; i++)
        if(i!=k&&p.x[k]==p.x[i]&&p.y[k]==p.y[i])
            return 0;
    return 1;
}
bool ncheck(node p)//判断越界和访问,0=未越界,未访问
{
    for(int i=0; i<4; i++)
        if(p.x[i]<0||p.x[i]>=8||p.y[i]<0||p.y[i]>=8)
            return 1;
    if(vis[p.x[0]][p.y[0]][p.x[1]][p.y[1]][p.x[2]][p.y[2]][p.x[3]][p.y[3]])
        return 1;
    return 0;
}
int bfs()
{
    node t,tt;
    queue<node> q;
    sp.step=0;
    ms(vis);
    vis[sp.x[0]][sp.y[0]][sp.x[1]][sp.y[1]][sp.x[2]][sp.y[2]][sp.x[3]][sp.y[3]]=1;
    q.push(sp);
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        if(t.step>=8)return 0;//这里是结束,不是继续
        if(check(t))return 1;
        for(int i=0; i<4; i++)
        {
            for(int j=0; j<4; j++)
            {
                tt=t,tt.step++;
                tt.x[i]+=dir[j][0],tt.y[i]+=dir[j][1];
                if(ncheck(tt))continue;//越界或者访问过
                if(judge(tt,i))//如果空
                {
                    if(check(tt))return 1;//如果已经是最终态
                    vis[tt.x[0]][tt.y[0]][tt.x[1]][tt.y[1]][tt.x[2]][tt.y[2]][tt.x[3]][tt.y[3]]=1;
                    q.push(tt);
                }
                else//如果非空的
                {
                    tt.x[i]+=dir[j][0],tt.y[i]+=dir[j][1];//再跳一格
                    if(ncheck(tt)||!judge(tt,i))continue;//还是非空,或者越界
                    if(check(tt))return 1;//如果已经是最终态
                    vis[tt.x[0]][tt.y[0]][tt.x[1]][tt.y[1]][tt.x[2]][tt.y[2]][tt.x[3]][tt.y[3]]=1;
                    q.push(tt);
                }
            }
        }
    }
    return 0;
}
int main()
{
    while(~scanf("%d%d",&sp.x[0],&sp.y[0]))
    {
        sp.x[0]--,sp.y[0]--;
        for(int i=1; i<4; i++)
        {
            scanf("%d%d",&sp.x[i],&sp.y[i]);
            sp.x[i]--,sp.y[i]--;
        }
        ms(mp);
        for(int i=0; i<4; i++)
        {
            scanf("%d%d",&ep.x[i],&ep.y[i]);
            ep.x[i]--,ep.y[i]--;
            mp[ep.x[i]][ep.y[i]]=1;
        }
        printf("%s\n",bfs()?"YES":"NO");
    }
    return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 1401 Solitaire(BFS)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址