این روش رو یه جور واضحتر قبلا شنیده بودم که باید به خونه ای رفت که از اون خونه به کمترین خونه های ممکن بشه رفت. حل مسئله: (اصل برنامه 20 خطه بقیش کارای گرافیکیه و ... است).
تابع shat3 کار خاصی انجام نمیده فقط یک صفحه شطرنجی در محیط تکست ایجاد می کشه . آرایه sh درسته که 12*12 هست ولی در واقع خود صفحه شطرنج هستش که به این صورت مقدار دهی اولیه کردم:
اینکار رو بخاطر این کردم که راحتتر بشه خارج شدن اسب از صفحه شطرنج رو چک کرد. خونه هایی که صفرند همون صفحه شطرنج رو تشکیل می دهند.
آرایه h هم که نحوه حرکت اسب رو شبیه سازی می کنه. هر کدوم از هشت جفت عددهای آرایه h یک حرکت اسب هست. و چون اسب از هر خونه حداکثر به هشت خانه بعدی می تونه بره پس آرایه h هشت جفت عدد داره.
این روش فقط چند حالت از میلیونها جواب رو میده. این سئوال رو قبلا در حالت کلیش رو مجبور بودم حل کنم یعنی تمام حالتهایی که اسب می تونه همه خونه ها رو در 64 حرکت بره . اینطوری خیلی سخت تر میشه این هم بعنوان یک سئوال بهش فکر کنید . من قبلا حل کردم (کلا تغییرش دادم تا جواب این سئوال رو بدم) البته برنامه با این روش راه حل های زیادی رو پیدا می کنه ولی نمی تونه همه راه حل ها رو پیدا کنه باید 64^8 حالت رو چک کنه که در حدود همون برنامه قبلی در میاد (یعنی یکسال). توی سه یا چهار ساعت 3000 تا جواب رو بدست میاره (بستگی به نقطه شروع داره) برای همین کل جواب ها باید بیشتر از چند میلیون باشه.
حالا همین خودش دوباره سئوال باشه. یعنی برنامه ای که بتونه تمام راه حل ها رو بدست بیاره. روش جالبی داره ولی سخت تره.
یه صفحه n در n داریم که بعضی از این خونه ها ورود ممنوع هست کوتاه ترین مسیر بین دو نقطه دلخواه A و B اگر فقط مجاز باشیم به سمت بالا و پاین و چپ راست حرکت کنیم و وارد خانه ها مموع نوشیم کدام است
برای راحتی n را 10 بگیرید و خانه های بلوکه شده و A B ه رو از کاربر در یافت کنید و مختصات خانه ها جواب به همراه طول مسیر رو چاپ کنید
#include<stdio.h>
#include<conio.h>
int board[10][10]={0},Ax,Ay,Bx,By;
int minBoard[10][10]={0},lMin=101;
void getABForbidenPlaces();
void find(int,int,int);
void main(){
int i,j;
clrscr();
getABForbidenPlaces();
find(Ax,Ay,0);
clrscr();
for(i=0;i<10;i++){
for(j=0;j<10;j++)
printf("%3d",minBoard[i][j]);
printf("\n");
}
getch();
}
void getABForbidenPlaces(){
int x,y;
do{
printf("Enter A x,y (0<x,y && x,y=<10) : ");
scanf("%d%d",&x,&y);
Ax=x;Ay=y;
}while(x<=0 || x>=10 || y<=0 || y>=10);
do{
printf("Enter B x,y (0<x,y && x,y=<10) : ");
scanf("%d%d",&x,&y);
Bx=x;By=y;
}while(x<=0 || x>=10 || y<=0 || y>=10 || board[Bx][By]==1);
printf("Enter forbiden x,y (for end enter zero or negative numbers) : ");
scanf("%d%d",&x,&y);
while (x>0 && x<=10 && y>0 && y<=10 && board[x][y]==0 ){
board[x][y]=-1;
printf("Enter forbiden x,y (for end enter zero or negative numbers) : ");
scanf("%d%d",&x,&y);
}
}
void find(int x,int y, int l){
int i,j;
if(x==Bx && y==By){
if(l<lMin){
for(i=0;i<10;i++)
for(j=0;j<10;j++)
minBoard[i][j]=board[i][j];
}
return;
}
if(x<0 || x>=10 || y<0 || y>=10 || board[x][y]!=0) return;
board[x][y]=l;
find(x+1,y ,l+1);
find(x ,y+1,l+1);
find(x-1,y ,l+1);
find(x ,y-1,l+1);
board[x][y]=0;
}
