【寛捜入門】8デジタル難題
ネット上でいろいろな解決方法を見て、自分が変わったと感じて、分かち合いましょう.
以下は原題です.
タイトルの説明
初期状態のステップ数は1でも、はは
入力:最初の3*3のマトリクスは元の状態で、2番目の3*3のマトリクスはターゲットの状態です.出力:移動に使用する最小ステップ数
Input
2 8 3 1 6 4 7 0 5 1 2 3 8 0 4 7 6 5
Output
6
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
テーマの绍介はあいまいで、大体の意味は:3×3のボードには、8つの駒が並べられており、各駒には1から8の数字が表示されています.碁盤にはスペースが1つ残っており、スペースは0で表されています.スペースの周りの駒はスペースに移動できます.(子供の頃携帯で遊んでいたパズルとは差が少ない)
解決策は幅優先探索であり,幅優先探索の万能テンプレートは以下の通りである(アルゴリズムノートから).
次に、上のコード:
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
構造体変数のstateおよびjudge関数の(i-state)を説明します.
マトリクス空格子点が1回移動すると、2 8 3 2 8 3 8 3 8 8 3 3 1 6 4—>1 6 4 4—>1 6 4 4 7 5 6 5 5 5 5 5 5 5 5 5が最初にアップシフト動作を行うように、次の移動が元に戻ることを防止するために、2回目のダウンシフト操作はマトリクスを元のものに戻すように繰り返してデッドサイクルをもたらすためシフト操作を記録する必要があり,map,配列などを用いる方法が多く,筆者の方法はよくないかもしれないが,1回目のアップシフトを2回目にするとダウンシフトできず,上下と左右が反発する.4つの位置の移動i=0,1,2,3はそれぞれ上,左,下,右,上と下が0,2,左と右が1,3を表し,両者の差はいずれも絶対値2現在の移動のパラメータiをstateで記録し,次の行移動時に絶対値(i-state)が2,2であるか否かを判断するのは合法ではない.
以下は原題です.
タイトルの説明
初期状態のステップ数は1でも、はは
入力:最初の3*3のマトリクスは元の状態で、2番目の3*3のマトリクスはターゲットの状態です.出力:移動に使用する最小ステップ数
Input
2 8 3 1 6 4 7 0 5 1 2 3 8 0 4 7 6 5
Output
6
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
テーマの绍介はあいまいで、大体の意味は:3×3のボードには、8つの駒が並べられており、各駒には1から8の数字が表示されています.碁盤にはスペースが1つ残っており、スペースは0で表されています.スペースの周りの駒はスペースに移動できます.(子供の頃携帯で遊んでいたパズルとは差が少ない)
解決策は幅優先探索であり,幅優先探索の万能テンプレートは以下の通りである(アルゴリズムノートから).
void BFS(int s){
queue q;
q.push(s);
while(!q.empty()){
top;
top;
;
top , ;
}
}
次に、上のコード:
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
構造体変数のstateおよびjudge関数の(i-state)を説明します.
マトリクス空格子点が1回移動すると、2 8 3 2 8 3 8 3 8 8 3 3 1 6 4—>1 6 4 4—>1 6 4 4 7 5 6 5 5 5 5 5 5 5 5 5が最初にアップシフト動作を行うように、次の移動が元に戻ることを防止するために、2回目のダウンシフト操作はマトリクスを元のものに戻すように繰り返してデッドサイクルをもたらすためシフト操作を記録する必要があり,map,配列などを用いる方法が多く,筆者の方法はよくないかもしれないが,1回目のアップシフトを2回目にするとダウンシフトできず,上下と左右が反発する.4つの位置の移動i=0,1,2,3はそれぞれ上,左,下,右,上と下が0,2,左と右が1,3を表し,両者の差はいずれも絶対値2現在の移動のパラメータiをstateで記録し,次の行移動時に絶対値(i-state)が2,2であるか否かを判断するのは合法ではない.
#include
#include
#include
using namespace std;
//
struct Node{
int a[3][3]; //
int y; //(y,x) 0
int x;
int step; //step
int state; //state ( )
}node;
int b[3][3]; // b
int t1[4]={-1,0,1,0};
int t2[5]={0,-1,0,1}; //0~4
//
bool judge(int y,int x,int i,int state){
if(y>2||y<0||x>2||x<0)
return false;
if(abs(i-state)==2)
return false;
return true;
}
// 0 ,
void exchange(int &a,int &b){
int temp;
temp=a;
a=b;
b=temp;
}
// b
bool equal(int a[3][3],int b[3][3]){
int i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++){
if(a[i][j]!=b[i][j])
return false;
}
return true;
}
void BFS(){
queue q;
q.push(node);
while(!q.empty()){ // ,
node=q.front(); // node , node
q.pop();
if(equal(node.a,b)) // ,
{
printf("%d
",node.step);
return;
}
for(int i=0;i<4;i++){ // 0 ,
int newY=node.y+t1[i];
int newX=node.x+t2[i];
if(judge(newY,newX,i,node.state)){ //
Node t=node;
exchange(t.a[node.y][node.x],t.a[newY][newX]); // ( )
t.y=newY;
t.x=newX;
t.step=node.step+1; // 1
t.state=i; //
q.push(t);
}
}
}
}
int main(){
int i,j;
for(i=0;i<3;i++) // , node
for(j=0;j<3;j++){
scanf("%d",&node.a[i][j]);
if(node.a[i][j]==0){ // 0,
node.state=10;
node.y=i;
node.x=j;
node.step=1;
}
}
for(i=0;i<3;i++) //
for(j=0;j<3;j++)
scanf("%d",&b[i][j]);
BFS();
return 0;
}