coba.cpp

algorithm bfs to solve knight tour problem

#include <queue>
#include <stdio.h>
#include <conio.h>

using namespace std;
struct Node
{
	int Row, Col, Step;
	Node(int r=0, int c=0, int s=0)
	{
		Row=r;
		Col=c;
		Step=s;
	}
};

int CountKnightPath(int KRow, int KCol, int DestRow, int DestCol)
{
	//jika sudah sampai pada langkah pertama
	if(KRow==DestRow && KCol==DestCol)
		return 0;
	queue<Node> q;

	bool Cell[8][8];		//board
	for(int i=0;i<8;i++)	//init board
	{
		for(int j=0;j<8;j++)
		{
			Cell[i][j]=false;
		}
	}

	int dr[8], dc[8];		//step
	dr[0]=-2; dc[0]=1;		//kanan atas 1
	dr[1]=-1; dc[1]=2;		//kanan atas 2
	dr[2]=1;  dc[2]=2;
	dr[3]=2;  dc[3]=1;
	dr[4]=2;  dc[4]=-1;
	dr[5]=1;  dc[5]=-2;
	dr[6]=-1; dc[6]=-2;
	dr[7]=-2; dc[7]=-1;

	Node Root(KRow, KCol);	//init knight
	q.push(Root);			//simpan
	Cell[KRow][KCol]=true;	//tandai

	while(!q.empty())
	{
		//ambil palig depan
		Node Current=q.front();
		q.pop();
		//untuk tiap kemungkinan langkah
		for (i=0;i<8;i++)
		{
			//cek valid board
			if(Current.Row+dr[i]>=0 && Current.Row+dr[i]<8 && Current.Col+dc[i]>=0 && Current.Col+dc[i]<8)
			{
				//cek sudah dijalani
				if(Cell[Current.Row+dr[i]][Current.Col+dc[i]]==false)
				{
					//buat node baru
					Node Child(Current.Row+dr[i],Current.Col+dc[i],Current.Step+1);
					//Jika node baru adalah kotak tujuan -->keluar, kembalikan jarak sekarang
					if(Child.Row==DestRow && Child.Col==DestCol) return Child.Step;
					else 
						q.push(Child);
				}
			}
		}
	}

	return -1;
}

void main()
{
	int Xawal, Yawal, Xtujuan, Ytujuan;
	printf("Posisi x knight mula-mula : "); scanf("%d", &Xawal);
	printf("Posisi y knight mula-mula : "); scanf("%d", &Yawal);
	printf("Posisi x knight tujuan : "); scanf("%d", &Xtujuan);
	printf("Posisi y knight tujuan : "); scanf("%d", &Ytujuan);

	int langkah=CountKnightPath(Yawal,Xawal,Ytujuan,Xtujuan);
	if(langkah==-1)
	{
		printf("Langkah tidak ditemukan");
	}
	else
		printf("Langkah yang dibutuhkan untuk sampai ke tujuan adalah %d langkah", langkah);
	getch();
}