程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1401 Solitaire

HDU 1401 Solitaire

編輯:C++入門知識

HDU 1401 Solitaire


 

Solitaire

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 12 Accepted Submission(s) : 1
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

Source Southwestern Europe 2002

 

雙向廣搜。 每組棋子的坐標為1~8 共有四個坐標 8個數都可以用三個二進制數保存 所以可以將狀態轉換為相應的十進制數進行狀態壓縮

只能走八步,每步有十六中變化 所以雙向廣搜可以解決

 

 

#include
#include
#include
#include
#include
#include
using namespace std;
struct Point
{
    int x,y;
    bool cheak()
    {
        if(x>=0&&x<8&&y>=0&&y<8)
            return true ;
        else return false ;
    }
};
struct node
{
    Point a[5];
    int t;
} st,ed,e;
int dir[4][2]= {0,1,0,-1,1,0,-1,0};
bool vis[16777216+1];  //標記  狀態壓縮
int us[65536+10];  //記錄出現過的狀態
int len;

bool cmp(Point n1,Point n2)
{
    return n1.x!=n2.x?n1.xus[mid])
            l=mid+1;
        else r=mid-1;
    }
    return false ;
}

void dfs()
{
    queueq;
    memset(vis,false ,sizeof(vis));
    len=0;
    int Hash;
    Hash=get_hash(st.a);
    vis[Hash]=true ;
    us[len++]=Hash;
    st.t=0;
    q.push(st);
    int k;
    //起點開始廣搜可以出現的狀態
    while(q.size())
    {
        st=q.front();
        q.pop();
        if(st.t>=4) continue ;
        for(int j=0; j<4; j++)
        {
            for(int i=0; i<4; i++)
            {
                e=st;
                e.t++;
                e.a[i].x+=dir[j][0];
                e.a[i].y+=dir[j][1];
                if(!e.a[i].cheak())
                    continue ;
                for(k=0; k<4; k++)
                {
                    if(k!=i&&e.a[k].x==e.a[i].x&&e.a[k].y==e.a[i].y)
                        break;
                }
                if(k==4)
                {
                    Hash=get_hash(e.a);
                    if(!vis[Hash])
                    {
                        vis[Hash]=true ;
                        us[len++]=Hash;
                        q.push(e);
                    }
                }
                else
                {
                    e.a[i].x+=dir[j][0];
                    e.a[i].y+=dir[j][1];
                    if(!e.a[i].cheak())
                        continue ;
                    for(k=0; k<4; k++)
                    {
                        if(k!=i&&e.a[k].x==e.a[i].x&&e.a[k].y==e.a[i].y)
                            break;
                    }
                    if(k==4)
                    {
                        Hash=get_hash(e.a);
                        if(!vis[Hash])
                        {
                            vis[Hash]=true ;
                            us[len++]=Hash;
                            q.push(e);
                        }
                    }
                }
            }
        }
    }
    sort(us,us+len);
    memset(vis,false ,sizeof(vis));
    Hash=get_hash(ed.a);
    if(fine(Hash))  //從起點走出現過這種狀態
    {
        printf(YES
);
        return ;
    }
    vis[Hash]=true ;
    q.push(ed);
    while(q.size())
    {
        st=q.front();
        q.pop();
        if(st.t>=4) continue ;
        for(int j=0; j<4; j++)
        {
            for(int i=0; i<4; i++)
            {
                e=st;
                e.t++;
                e.a[i].x+=dir[j][0];
                e.a[i].y+=dir[j][1];
                if(!e.a[i].cheak())
                    continue ;
                for(k=0; k<4; k++)
                {
                    if(k!=i&&e.a[k].x==e.a[i].x&&e.a[k].y==e.a[i].y)
                        break;
                }
                if(k==4)
                {
                    Hash=get_hash(e.a);
                    if(fine(Hash))
                    {
                        printf(YES
);
                        return ;
                    }
                    if(!vis[Hash])
                    {
                        vis[Hash]=true ;
                        q.push(e);
                    }
                }
                else
                {
                    e.a[i].x+=dir[j][0];
                    e.a[i].y+=dir[j][1];
                    if(!e.a[i].cheak()) continue ;
                    for(k=0; k<4; k++)
                    {
                        if(k!=i&&e.a[k].x==e.a[i].x&&e.a[k].y==e.a[i].y)
                            break;
                    }
                    if(k!=4) continue ;
                    Hash=get_hash(e.a);
                    if(fine(Hash))
                    {
                        printf(YES
);
                        return ;
                    }
                    if(!vis[Hash])
                    {
                        vis[Hash]=true ;
                        q.push(e);
                    }
                }
            }
        }
    }
    printf(NO
);
    return ;
}

int main()
{
    while(~scanf(%d%d,&st.a[0].x,&st.a[0].y))
    {
        for(int i=1; i<4; i++)
            scanf(%d%d,&st.a[i].x,&st.a[i].y);
        st.t=0;
        for(int i=0; i<4; i++)
            scanf(%d%d,&ed.a[i].x,&ed.a[i].y);
        ed.t=0;
        //將坐標轉為0~7對應2^3-1的數  狀態壓縮
        for(int i=0; i<4; i++)
        {
            st.a[i].x--;  
            st.a[i].y--;
            ed.a[i].x--;
            ed.a[i].y--;
        }
        dfs();
    }
    return 0;
}


 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved