main.cpp

This is bfs program..

#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
	// apabila awal == tujuan, maka di return 0
	if(krow==destrow && kcol==destcol)
		return 0;

	queue<node> q;
	bool cell[8][8];   //buat board/papa
	for(int i=0;i<8;i++)
	{
		for(int j=0;j<8;j++)
		{
			cell[i][j]=false;
		}
	}

	int dr[8],dc[8];
	dr[0]=-2; dc[0]=1;
	dr[1]=-1; dc[1]=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);
	cell[krow][kcol]=true;

	while(!q.empty())
	{
		//ambil paling 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;
					
					//jika tidak, simpan langkah selanjutnya
					else q.push(child);
				}
			}
		}

	}

	return -1;

}

void main()
{	
	int xawal, yawal, xtujuan, ytujuan,langkah;

	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);

	xawal=xawal-1;
	yawal=yawal-1;
	xtujuan=xtujuan-1;
	ytujuan=ytujuan-1;
	langkah = countknightpath(yawal,xawal,ytujuan,xtujuan);
	if (langkah==-1)
	{
		printf("Langkah tidak ditemukan");
	}

	else
	{

		printf("Langkah yang dibutuhkan untuk sampai tujuan : %d langkah", langkah);
	}

	getch();
}