2 đoạn code dưới đây là bài " Mã đi tuần "
đoạn code của em
Code:
#include<iostream>
#include<conio.h>
using namespace std;
short kt;
short a[8]={-1,-2,-2,-1,1,2,2,1};
short b[8]={-2,-1,1,2,2,1,-1,-2};
void Input(short &row,short &col)
{
cout<<"kich thuoc : ";cin>>kt;
cout<<"dong va cot : ";cin>>row>>col;
}
void Output(short *CB)
{
for(short i=0;i<kt;++i)
{
for(short j=0;j<kt;++j)
cout<<*(CB+i*kt+j)<<'\t';
cout<<'\n';
}
exit(1);
}
bool Available(short *CB,short row,short col) // kiem tra vi tri dong ROW cot COL co di duoc ko
{
return(0<=row && row<kt && 0<=col && col<kt && *(CB+row*kt+col)==0);
}
void Try(short *CB,short row,short col,short so) // xet vi tri dong ROW cot COL tren ban co
{
++so; *(CB+row*kt+col)=so; // danh dau vi tri nay ko the di duoc nua
short i;
for(i=0;i<8;++i)
if(Available(CB,row+a[i],col+b[i]))
if(so==kt*kt-1) Output(CB) ; else Try(CB,row+a[i],col+b[i],so);
//QUAY LUI
*(CB+row*kt+col)=0; --so;
}
void Solution(short row,short col) // bat dau tu vi tri dong ROW cot COL
{
short *M=new short[kt*kt]; // tao 1 ma tran danh dau cac o da di qua
for(short i=0;i<kt*kt;++i) *(M+i)=0; // danh dau chua co o nao di qua
Try(M,row,col,0);
cout<<"Impossible!!\n\n";
}
void main()
{
short rowStart,colStart;
Input(rowStart,colStart);
Solution(rowStart,colStart);
}
..và đoạn code trong sách
Code:
#include<iostream>
using namespace std;
short i,j,n;
bool q;
short a[8],b[8];
short h[8][8];
void input(short &kt,short &row,short &col)
{
cout<<"Kich thuoc ban co : "; cin>>kt;
cout<<"Vi tri xuat phat : ";cin>>row>>col;
}
void output()
{
for(i=0;i<n;++i)
{
for(j=0;j<n;++j) cout<<h[i][j]<<'\t';
cout<<'\n';
}
}
void Try(short so,short x,short y)
{
short u,v,k=-1;
do
{
++k; q=false;
u=x+a[k]; v=y+b[k];
if(0<=u && u<n && 0<=v && v<n && h[u][v]==0)
{
h[u][v]=so;
if(so<n*n) { Try(so+1,u,v) ; if(q==false)h[u][v]=0; }
else
q=true;
}
}
while(k<7 && q==false);
}
void main()
{
short rowStart,colStart;
a[0]=-1; b[0]=-2;
a[1]=-2; b[1]=-1;
a[2]=-2; b[2]=1;
a[3]=-1; b[3]=2;
a[4]=1; b[4]=2;
a[5]=2; b[5]=1;
a[6]=2; b[6]=-1;
a[7]=1; b[7]=-2; q=false;
for(i=0;i<n;++i)
for(j=0;j<n;++j) h[i][j]=0;
input(n,rowStart,colStart);
h[rowStart][colStart]=1;
Try(2,rowStart,colStart);
if(q)output(); else cout<<"CAN'T \n\n";
}
thuật toán là như nhau , sao code của em lại chạy chậm hơn code trong sách hic hic
cho em hỏi thêm , có ai có thuật cải tiến cho bài Mã đi tuần ko ( có thể chạy với bàn cờ bự ),em cũng biết cải tiến nó chút ít nhưng chạy cũng ko hoàn hảo ( chỉ chạy nhanh ở 1 số trường hợp , tất nhiên là vẫn nhanh hơn thuật cũ )