Chương trình mã đi tuần

[nguyenhuuca (Nguyen Ca)]

Tiếp từ topic này Chương trình minh họa giải thuật Dijkstra tìm đường đi ngắn nhất

/*****************************************************************************
* Chuong trinh C1-5: Chuong trinh Ma Di Tuan                                  *
* Phuong phap giai: dung phuong phap de qui de giai quyet van de theo kieu   *
		              lan nguoc (backtracking)                                 *
* Nguoi viet chuong trinh: Nguyen Hong Chuong                                *
* Ngay cap nhat moi nhat: 15/3/1999                                          *
*****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define KICHTHUOC 5  // Kich thuoc cua ban co

void nuocdi(int, int, int);
void innuocdi(int BanCo[][KICHTHUOC]);
void vebanco(void);

// To chuc ban co la mang hai chieu
int BanCo[KICHTHUOC][KICHTHUOC];

// 8 cach di cua con ma
int a[8] = {2,  2,  1, -1, -2, -2, -1,  1};
int b[8] = {1, -1, -2, -2, -1,  1,  2,  2};

int SoLoiGiai = 0;

int main(void)
{
   int i, j, m, n;

   clrscr();
   vebanco();

   for(i = 0; i < KICHTHUOC; i++)
      for(j = 0; j < KICHTHUOC; j++)
      {
	      // Khoi dong tat ca cac o tren ban co deu chua di
	      for(m = 0; m < KICHTHUOC; m++)
	         for(n = 0; n < KICHTHUOC; n++)
	            BanCo[m][n] = 0;

	      // Chon nuoc di dau tien va goi ham de qui de di nuoc thu hai
	      BanCo[i][j] = 1;
	      nuocdi(2, i, j);
      }
   return 0;
}

// Ham NuocDi giup di nuoc thu n xuat phat tu o(x, y)
void nuocdi(int n, int x, int y)
{
   int i;
   char c;
   for(i = 0; i < 8; i++)
   {
      if(BanCo[x+a[i]][y+b[i]] == 0 && x+a[i] >= 0 && x+a[i] < KICHTHUOC
				    && y+b[i] >= 0 && y+b[i] < KICHTHUOC)
      {
	      // Di nuoc thu n
	      BanCo[x+a[i]][y+b[i]] = n;

	      if(n == KICHTHUOC*KICHTHUOC)  // Dkien dung, di duoc nuoc cuoi
	      {
	         innuocdi(BanCo);
	         gotoxy(43, 4);
	         printf("         Loi giai thu %d", ++SoLoiGiai);
	         gotoxy(13, 25);
	         printf("Nhan <ENTER> de tiep tuc tim loi giai ke. Nhan <ESC> de thoat");
	         if(c = getch() == 27)
	            exit(1);
	      }
	      else                          // Buoc de qui, goi di nuoc n+1
	         nuocdi(n+1, x+a[i], y+b[i]);

	      // lan nguoc
	      BanCo[x+a[i]][y+b[i]] = 0;
	      innuocdi(BanCo);
	      gotoxy(43, 4);
	      printf("Dang tim loi giai thu %d", SoLoiGiai+1);
	      gotoxy(13, 25);
	      printf("   Xin vui long cho doi, nhan phim <Ctrl-Break> de thoat...    ");
      }
   }
}

void innuocdi(int BanCo[][KICHTHUOC])
{
   int i, j;
   char c;
   randomize();
   textmode(C80);
   textbackground(BLACK);
   textcolor(1);
   for(i = 0; i < KICHTHUOC; i++)
      for(j = 0; j < KICHTHUOC; j++)
      {
	      gotoxy(23+5*j, 8+2*i);
	      textcolor(1 + random(15));
	      if(BanCo[i][j] == 0 ? printf("  ") : cprintf("%2d", BanCo[i][j]));
      }
}

void vebanco()
{
   printf("\n\t\t\t     CHUONG TRINH MA DI TUAN\n");
   printf("\n\t\tKich thuoc ban co %dx%d", KICHTHUOC, KICHTHUOC);
   printf("\n\n\t\t       1    2    3    4    5    6    7    8");
   printf("\n\t\t    ÚÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄ¿");
   printf("\n\t\t 1  ³    ³    ³    ³    ³    ³    ³    ³    ³");
   printf("\n\t\t    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
   printf("\n\t\t 2  ³    ³    ³    ³    ³    ³    ³    ³    ³");
   printf("\n\t\t    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
   printf("\n\t\t 3  ³    ³    ³    ³    ³    ³    ³    ³    ³");
   printf("\n\t\t    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
   printf("\n\t\t 4  ³    ³    ³    ³    ³    ³    ³    ³    ³");
   printf("\n\t\t    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
   printf("\n\t\t 5  ³    ³    ³    ³    ³    ³    ³    ³    ³");
   printf("\n\t\t    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
   printf("\n\t\t 6  ³    ³    ³    ³    ³    ³    ³    ³    ³");
   printf("\n\t\t    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
   printf("\n\t\t 7  ³    ³    ³    ³    ³    ³    ³    ³    ³");
   printf("\n\t\t    ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
   printf("\n\t\t 8  ³    ³    ³    ³    ³    ³    ³    ³    ³");
   printf("\n\t\t    ÀÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÙ");
}