Mọi người cho em hỏi sao Code của em không hiện ra đường đi ngắn nhất mà lại hiện ra tất cả các giá trị nằm trong Queue ạ.
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#include"Mqueue.h"
#define SIZE 9
#define SIZE_QUEUE_DATA_RX 256
#if (SIZE_QUEUE_DATA_RX & (SIZE_QUEUE_DATA_RX - 1)) != 0
#error "SIZE_QUEUE_DATA_RX must be a power of two"
#endif
bool visited[SIZE * SIZE];
int back[SIZE * SIZE];
// Check tọa độ bất kỳ có thuộc ma trận
bool Check_toado(int toadox, int toadoy)
{
if((toadox >= 0 && toadox <SIZE) && (toadoy >= 0 && toadoy <SIZE)) return true;
else return false;
}
// Tìm kiếm các vị trí xung quanh điểm đang xét có giá trị là 1
void Check_point(int point, int point_t[], Queue *queue, int back[])
{
// Check tọa độ trái
if(point_t[point -1] == 1 && point % SIZE != 0 && visited[point -1] == false)
{
enqueue(queue, point-1);
back[point - 1] = point;
visited[point -1] = true;
}
//Check tọa độ phải
if(point_t[point +1] == 1 && (point + 1) % SIZE != 0 && visited[point + 1] == false)
{
enqueue(queue, point+1);
back[point + 1] = point;
visited[point +1] = true;
}
//Check tọa độ trên
if(point_t[point - SIZE] == 1 && point > SIZE -1 && visited[point - SIZE] == false)
{
enqueue(queue, point-1);
back[point - SIZE] = point;
visited[point - SIZE] == true;
}
//Check tọa độ dưới
if(point_t[point + SIZE] == 1 && point < (SIZE - 1) * SIZE && visited[point + SIZE] == false)
{
enqueue(queue, point + SIZE);
back[point + SIZE] = point;
visited[point + SIZE] = true;
}
}
void Print_Path(int u, int v, int back[])
{
if(u == v)
{
printf("v ");
}
else
{
if(back[v] == -1)
printf("Khong co duong di");
else
Print_Path(u,back[v],back);
}
}
void BFS(int start, int end, Queue * queue, int point_t[], int back[])
{
enqueue(queue, start);
visited[start] = true;
back[start] = start;
while(!isEmpty(queue))
{
int u = front(queue);
dequeue(queue);
Check_point(u, point_t, queue, back);
}
Print_Path(start, end, back);
}
int main()
{
/*
srand : Ramdom các giá trị của ma trận là 0 hoặc 1.
matran[][] : Biến dùng để lưu ma trận.
i, j: Các biên đếm.
point_t: Quy tọa độ về mảng 1 chiều được đánh dấu từ 0 tới hết và tắng dần từ trái qua phải, từ trên xuống dưới.
Vd: (0,0)= 0, (0,1) = 1,.....
*/
srand(int(time(0)));
int matran[SIZE][SIZE];
int point_t[SIZE * SIZE];
int toadox, toadoy;
int i = 0, j = 0;
FILE * file;
// Enter Mattrix
/*
Ramdom các giá trị của ma trận
Lấy giá trị cho các tọa độ
*/
// file = fopen("matran.txt","r");
for(i = 0; i < SIZE; i++)
{
for(j = 0; j < SIZE; j++)
{
// if(i == 0 && j == 0) matran[i][j] = 1;
// matran[i][j] = 0 + rand() % 2;
scanf("%d", &matran[i][j]);
point_t[i * SIZE +j] = matran[i][j];
visited[i*SIZE + j] = false;
back[i*SIZE +j] = -1;
}
}
// Print Mattrix
for(i = 0; i < SIZE; i++)
{
for(j = 0; j < SIZE; j++)
{
printf("%d ", matran[i][j]);
}
printf("\n");
}
// Enter toa do diem bat ky
printf("Nhap toa do diem bat ky: ");
scanf("%d%d", &toadox, &toadoy);
//Check toa do diem bat ky
if(Check_toado(toadox,toadoy) != false) printf("Toa do thuoc ma tran.\n");
else printf("Toa do khong thuoc ma tran\n");
// Printf Point_t
printf("\n Ma tran diem: \n");
for(i = 0; i < SIZE; i++)
{
for(j = 0; j < SIZE; j++)
{
printf("%d ", i * SIZE +j);
}
printf("\n");
}
printf("\nPoint bat ky : %d\n", toadoy * SIZE +toadox);
// Createqueue
struct Queue *queue = createQueue(1000);
// Sử dụng BFS để tìm đường đi ngắn nhất
BFS(0,toadoy * SIZE + toadox, queue, point_t, back);
return 0;
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?