coba.zip_bfs

#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(); }