zztanzzthanhzz Thành viên cấp 2
Tổng số bài gửi : 126 Join date : 17/07/2009 Age : 33 Đến từ : CNTT1 K9
| Tiêu đề: Bài Toán Mã Đi Tuần. Tue Mar 16, 2010 3:12 am | |
| | | | | Bài toán mã đi tuần, code của bạn đã giải quyết được với bàn cờ kích thước bao nhiêu? 5x5 hay là 6x6 ???
Với code được học trên lớp thì chỉ có thể giải quyết được dữ liệu cỡ đó là cùng!
Tuy nhiên hiện nay người ta có code giải quyết được bàn cờ 100x100. Các bạn có tin nổi không?
Mình chỉ mới viết được code giải quyết với kích thước bàn cờ trên 20 thôi! Các bạn cùng bàn luận nhé!
Code có dùng cấp phát động: (khá rõ ràng, dễ hiểu, giải quyết được bàn cờ tối đa 20x20) - Code:
-
// DuongTanThanh.Net // Sdt: 0169.736.4746 // Yahoo: khongthengungchat
#include <stdio.h> #include <conio.h> #include <stdlib.h> #define max 100 #define fo "madituan.out"
FILE *f; int X[8]={-2,-2,-1,1,2,2,1,-1}, Y[8]={-1,1,2,2,1,-1,-2,-2}, sodong, socot, dd[max][max], csdong, cscot, sonuocdi;
typedef struct vitri{ int bac, csd, csc; }; typedef struct node{ vitri info; node *next; }; typedef struct list{ node *pHead, *pTail; };
void input(){ printf("Nhap so dong: ");scanf("%d",&sodong); printf("Nhap so cot: ");scanf("%d",&socot); printf("Nhap toa do cua quan Ma:\n"); printf("x = ");scanf("%d",&csdong); printf("y = ");scanf("%d",&cscot); for (int i=0; i<sodong; i++) for (int j=0; j<socot; j++) dd[i][j]=0; sonuocdi = 1; dd[csdong][cscot] = 1; }
int in(int i, int j){ if ((0<=i)&&(i<sodong)&&(0<=j)&&(j<socot)) return 1; return 0; }
void push(list &l, node *p){ if (l.pHead==NULL) l.pHead=l.pTail=p; else{ p->next=l.pHead; l.pHead=p; } }
node *getnode (int bac, int csd, int csc){ vitri o; o.bac = bac; o.csd = csd; o.csc = csc; node *p= new node; p->info = o; p->next = NULL; return p; }
int bac (int x, int y){ int b=0; for (int i=0; i<8; i++) if (in(x+X[i], y+Y[i])&&(dd[x+X[i]][y+Y[i]]==0)) b++; return (b); }
void interchange(list &l){ node *p=l.pHead; while (p != NULL){ node *q=p->next; while (q != NULL){ if (q->info.bac < p->info.bac){ vitri temp=q->info; q->info = p->info; p->info = temp; } q = q->next; } p = p->next; } }
list getlist(int csd, int csc){ list l; l.pHead=l.pTail=NULL; for (int i=0; i<8; i++) if (in(csd+X[i], csc+Y[i])&&(dd[csd+X[i]][csc+Y[i]]==0)){ node *p = getnode(bac(csd+X[i], csc+Y[i]), csd+X[i], csc+Y[i]); push(l, p); } interchange(l); return l; }
void output(int kq[max][max]){ f=fopen(fo,"w"); for (int i=0; i<sodong; i++){ for (int j=0; j<socot; j++){ fprintf(f,"%4d",kq[i][j]); } fprintf(f,"\n"); } fclose(f); printf("Xem ket qua o file MaDiTuan.Out"); getch(); exit(1); }
void doing(int csd, int csc){ list l = getlist(csd, csc); while (l.pHead!=NULL){ sonuocdi++; dd[l.pHead->info.csd][l.pHead->info.csc] = sonuocdi; doing(l.pHead->info.csd, l.pHead->info.csc); dd[l.pHead->info.csd][l.pHead->info.csc] = 0; sonuocdi--; node *p = l.pHead; l.pHead = p->next; delete(p); } if (sonuocdi == sodong*socot) output(dd); }
void main(){ clrscr(); input(); doing(csdong, cscot); printf("Khong tim thay duong di nao thoa man bai toan MA DI TUAN"); getch(); } Code không dùng cpđ: (khó hiểu hơn, giải quyết được bàn cờ tối đa 26x27): - Code:
-
// DuongTanThanh.Net // Sdt: 0169.736.4746 // Yahoo: khongthengungchat
#include <stdio.h> #include <conio.h> #include <stdlib.h> #define max 100 #define fo "madituan.out"
FILE *f; int X[8]={-2,-2,-1,1,2,2,1,-1}, Y[8]={-1,1,2,2,1,-1,-2,-2}, sodong, socot, dd[max][max], csdong, cscot, sonuocdi;
void input(){ printf("Nhap so dong: ");scanf("%d",&sodong); printf("Nhap so cot: ");scanf("%d",&socot); printf("Nhap toa do cua quan Ma:\n"); printf("x = ");scanf("%d",&csdong); printf("y = ");scanf("%d",&cscot); for (int i=0; i<sodong; i++) for (int j=0; j<socot; j++) dd[i][j]=0; sonuocdi = 1; dd[csdong][cscot] = 1; }
int in(int i, int j){ if ((0<=i)&&(i<sodong)&&(0<=j)&&(j<socot)) return 1; return 0; }
int bac (int x, int y){ int b=0; for (int i=0; i<8; i++) if (in(x+X[i], y+Y[i])&&(dd[x+X[i]][y+Y[i]]==0)) b++; return (b); }
void swap(int list[8][3], int x, int y){ int temp; for (int i=0; i<3; i++){ temp=list[x][i]; list[x][i]=list[y][i]; list[y][i]=temp; } }
void bubble(int list[8][3], int spt){ for (int i=0; i<spt-1; i++) for (int j=spt-1; j>i; j--) if (list[j][0]<list[j-1][0]) swap(list,j,j-1); }
void create(int x, int y, int list[8][3], int &spt){ spt=0; for (int i=0; i<8; i++) if (in(x+X[i], y+Y[i])&&(dd[x+X[i]][y+Y[i]]==0)){ list[spt][0]= bac(x+X[i], y+Y[i]); list[spt][1]= x+X[i]; list[spt][2]= y+Y[i]; spt++; } bubble(list, spt); }
void output(int kq[max][max]){ f=fopen(fo,"w"); for (int i=0; i<sodong; i++){ for (int j=0; j<socot; j++){ fprintf(f,"%4d",kq[i][j]); } fprintf(f,"\n"); } fclose(f); printf("Xem ket qua o file MaDiTuan.Out"); getch(); exit(1); }
void doing(int csd, int csc){ if (sonuocdi == sodong*socot) output(dd);
int list[8][3], spt; create(csd, csc, list, spt);
for (int i=0; i<spt; i++){ sonuocdi++; dd [list[i][1]] [list[i][2]] = sonuocdi; doing(list[i][1], list[i][2]); dd [list[i][1]] [list[i][2]] = 0; sonuocdi--; } }
void main(){ clrscr(); input(); doing(csdong, cscot); printf("Khong tim thay duong di nao thoa man bai toan MA DI TUAN"); getch(); } | | | | |
|
|
zztanzzthanhzz Thành viên cấp 2
Tổng số bài gửi : 126 Join date : 17/07/2009 Age : 33 Đến từ : CNTT1 K9
| Tiêu đề: Re: Bài Toán Mã Đi Tuần. Tue Mar 16, 2010 3:15 am | |
| |
|
cutuan527 Moderators
Tổng số bài gửi : 1051 Join date : 26/04/2009 Age : 33 Đến từ : Vĩnh Long
| Tiêu đề: Re: Bài Toán Mã Đi Tuần. Tue Mar 16, 2010 2:07 pm | |
| |
|
zztanzzthanhzz Thành viên cấp 2
Tổng số bài gửi : 126 Join date : 17/07/2009 Age : 33 Đến từ : CNTT1 K9
| Tiêu đề: Re: Bài Toán Mã Đi Tuần. Tue Mar 16, 2010 10:41 pm | |
| |
|
Sponsored content
| Tiêu đề: Re: Bài Toán Mã Đi Tuần. | |
| |
|