http://noi.openjudge.cn/——2.5基本算法之搜索——200:Solitaire

题目

总时间限制: 5000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB
描述
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.
输入
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.
输出
The output should contain one word 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.
样例输入
4 4 4 5 5 4 6 5
2 4 3 3 3 6 4 6
样例输出
YES

宽搜代码

#include <bits/stdc++.h>
using namespace std;
const int d[4][2]={{0,-1},{-1,0},{0,1},{1,0}};//左上右下四个方向 
struct node{//每个棋的坐标 int x,y;bool operator<(const node& b)const{//排序用 if(x==b.x)return y<b.y;return x<b.x;}
};
struct chesss{int step,id[2];//步数 node piece[2][4];//起始和目标四个子的位置 bool board[2][9][9];//起始和目标的布局chesss(){//无参构造函数 step=0;memset(board,0,sizeof(board));//初始化 }void makeid(int x){//布局(各棋子的坐标)转换成8位唯一的id sort(piece[x],piece[x]+4);//排序 id[x]=0;for(int i=0;i<4;i++)id[x]=id[x]*100+piece[x][i].x*10+piece[x][i].y;}bool move(int i,int f){//哪个棋往哪个方向走棋 int& x=piece[0][i].x;//引用，给变量取别名 int& y=piece[0][i].y;//简化变量名称 int x2=piece[0][i].x+d[f][0],y2=piece[0][i].y+d[f][1],//一步 x3=piece[0][i].x+2*d[f][0],y3=piece[0][i].y+2*d[f][1];//两步 if(x2<1||x2>8||y2<1||y2>8)return 0;//一步越界if(board[0][x2][y2]){//旁边有子 if(x3<1||x3>8||y3<1||y3>8)return 0;//两步越界if(board[0][x3][y3])return 0;//跳步有子swap(board[0][x][y],board[0][x3][y3]);//跳步 x=x3,y=y3;//return 1;}else{//如果旁边没有棋子的话 swap(board[0][x][y],board[0][x2][y2]);//走一步 x=x2,y=y2;// return 1; }}void view(string s,int x,int w,int f){cout<<s<<"\t步数"<<step<<endl;if(w!=-1&&f!=-1)cout<<w<<"棋子"<<"\t"<<(f==0?"左":f==1?"上":f==2?"右":"下")<<endl; cout<<"列：\t";for(int j=1;j<=8;j++)cout<<j<<"\t";cout<<endl;for(int i=1;i<=8;i++){cout<<i<<"\t";for(int j=1;j<=8;j++)cout<<board[x][i][j]<<"\t";cout<<endl;}}
}chess,che;
//bool k[88888888];//88888888字节/1024/1024=84.77M
bool k[8][8][8][8][8][8][8][8];//8^8=16777216字节/1024/1024=16M
queue<chesss> q;
int main(){//freopen("data.cpp","r",stdin);//freopen("data.txt","w",stdout);int x,y;for(int i=0;i<2;i++){for(int j=0;j<4;j++){cin>>x>>y;chess.piece[i][j].x=x,chess.piece[i][j].y=y;chess.board[i][x][y]=1;}chess.makeid(i);//chess.view("原",i,-1,-1);}bool ans=0;q.push(chess);k[chess.piece[0][0].x-1][chess.piece[0][0].y-1][chess.piece[0][1].x-1][chess.piece[0][1].y-1][chess.piece[0][2].x-1][chess.piece[0][2].y-1][chess.piece[0][3].x-1][chess.piece[0][3].y-1]=1; while(!q.empty()){chess=q.front();q.pop();if(chess.step>8)continue;//cout<<chess.id[0]<<"\t"<<chess.id[1]<<endl;if(chess.id[0]==chess.id[1]){ans=1;break;}//chess.view("出发------------",0,-1,-1);for(int i=0;i<4;i++)//四个棋子 for(int j=0;j<4;j++){//四个方向 che=chess;if(che.move(i,j)){che.makeid(0);if(k[che.piece[0][0].x-1][che.piece[0][0].y-1][che.piece[0][1].x-1][che.piece[0][1].y-1][che.piece[0][2].x-1][che.piece[0][2].y-1][che.piece[0][3].x-1][che.piece[0][3].y-1])continue; k[che.piece[0][0].x-1][che.piece[0][0].y-1][che.piece[0][1].x-1][che.piece[0][1].y-1][che.piece[0][2].x-1][che.piece[0][2].y-1][che.piece[0][3].x-1][che.piece[0][3].y-1]=1; che.step++;//che.view("到达",0,i,j); q.push(che);}}}if(ans)cout<<"YES";else cout<<"NO";return 0;
}

总结

1.***
四个棋子，只改变他们的位置
可以上下左右移动一格
如果上下左右有别的棋子，可以跳过去
2.***
四个棋子坐标排序后生成唯一的id
3.***
bool k[88888888];//88888888字节/1024/1024=84.77M
bool k[8][8][8][8][8][8][8][8];//8^8=16777216字节/1024/1024=16M
4.***
宽搜找最短路径
在8步内深搜做不到枚举，较麻烦
5.***
需要验证局部程序。