[TIOJ] 1198. 8-puzzle

題目連結:http://tioj.infor.org/problems/1198

---

經典的8-puzzle問題，那就來寫個IDA*吧，不過要注意一下你推過來就別推回去，這樣是沒意義的XD(其實就是各種剪枝然後dfs)

#include <bits/stdc++.h>
using namespace std;
#define INF 21474836

int final[3][3];
int cur[3][3];
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
int pre[]={1,0,3,2};

int ida_star(int,int,int);
inline bool isOK(int,int);

int main(){
	cin.tie(0);ios_base::sync_with_stdio(0);
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>cur[i][j];
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>final[i][j];
	for(int i=1;i<=INF;i*=2){
		int test=ida_star(0,i,-1);
		if(test!=INF){
			cout<<test;
			break;
		}
	}
	return 0;
}

int ida_star(int cnt, int MAX,int howto){
	int xx,yy,h=0;bool flag=1;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(cur[i][j]==0){xx=i;yy=j;}
			if(cur[i][j]!=final[i][j]){flag=0;h++;}
		}
	}
	if(cnt+h>MAX)return INF;
	if(flag)return cnt;
	int rr=INF;
	for(int i=0;i<4;i++){
		if(isOK(xx+dx[i], yy+dy[i])&&pre[i]!=howto){
			swap(cur[xx][yy], cur[xx+dx[i]][yy+dy[i]]);
			rr=min(ida_star(cnt+1,MAX,i),rr);
			swap(cur[xx][yy], cur[xx+dx[i]][yy+dy[i]]);
		}
	}
	return rr;
}

inline bool isOK(int x,int y){
	return ((0<=x&&x<3)&&(0<=y&&y<3));
}#include <bits/stdc++.h>
using namespace std;
#define INF 21474836

int final[3][3];
int cur[3][3];
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
int pre[]={1,0,3,2};

int ida_star(int,int,int);
inline bool isOK(int,int);

int main(){
	cin.tie(0);ios_base::sync_with_stdio(0);
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>cur[i][j];
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>final[i][j];
	for(int i=1;i<=INF;i*=2){
		int test=ida_star(0,i,-1);
		if(test!=INF){
			cout<<test;
			break;
		}
	}
	return 0;
}

int ida_star(int cnt, int MAX,int howto){
	int xx,yy,h=0;bool flag=1;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(cur[i][j]==0){xx=i;yy=j;}
			if(cur[i][j]!=final[i][j]){flag=0;h++;}
		}
	}
	if(cnt+h>MAX)return INF;
	if(flag)return cnt;
	int rr=INF;
	for(int i=0;i<4;i++){
		if(isOK(xx+dx[i], yy+dy[i])&&pre[i]!=howto){
			swap(cur[xx][yy], cur[xx+dx[i]][yy+dy[i]]);
			rr=min(ida_star(cnt+1,MAX,i),rr);
			swap(cur[xx][yy], cur[xx+dx[i]][yy+dy[i]]);
		}
	}
	return rr;
}

inline bool isOK(int x,int y){
	return ((0<=x&&x<3)&&(0<=y&&y<3));
}