30/09/2018, 19:55
Tìm đường trong mê cung
Các anh chị xem giúp em bài này ạ !
Đề bài là tìm đường đi trong ma trận bằng Backtracking . đi được qua số 1.
Ý tưởng của em là lập 2 ma trận , 1 ma trận chứa ma trận gốc , 1 ma trận lưu lại số phương hướng tại từng điểm có thể di chuyển ví dụ như :
1 1 1
0 0 1
thì ma trận tương ứng là :
1 2 2
0 0 1
Ma trận gốc của em
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0
0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0
1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0
1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0
0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0
1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0
1 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 0 0 1
1 1 1 1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 1
1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1
1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 0 0 0 1
1 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1
1 1 1 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1 1 1
Nhưng khi chạy nó lại bị lỗi runtime mà em không hiểu lỗi ở đâu ?? Mong anh chị giúp ạ ?
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
int a[17][19],b[17][19];
int sang_phai(int i,int j);
int sang_trai(int i,int j);
int di_xuong(int i,int j);
FILE *f;
void khanang(int i,int j)
{
if(a[i+1][j]==1&&(i+1)<17&&a[i][j]) b[i][j]++;
if(a[i-1][j]==1&&(i-1)>=0&&a[i][j]) b[i][j]++;
if(a[i][j+1]==1&&(j+1)<19&&a[i][j]) b[i][j]++;
if(a[i][j-1]==1&&(j-1)>=0&&a[i][j]) b[i][j]++;
}
void timduong(int i,int j)
{
if(i==16&&j==18) return;
if(sang_phai(i,j))
{
b[i][j]--;
return timduong(i,j+1);
}
else
{
if(di_xuong(i,j))
{
b[i][j]--;
return timduong(i+1,j);
}
else
{
if(sang_trai(i,j))
{
b[i][j]--;
return timduong(i,j-1);
}
else
{
b[i][j]--;
return timduong(i-1,j);
}
}
}
}
int di_len(int i,int j)
{
if(a[i-1][j]==1&&b[i+1][j]!=0&&(i-1)>=0) return 1;
return 0;
}
int di_xuong(int i,int j)
{
if(a[i+1][j]==1&&b[i-1][j]!=0&&(i+1)<17) return 1;
return 0;
}
int sang_phai(int i,int j)
{
if(a[i][j+1]==1&&b[i][j+1]!=0&&(j+1)<19) return 1;
return 0;
}
int sang_trai(int i,int j)
{
if(a[i][j-1]==1&&b[i][j-1]!=0&&(j-1)>=0) return 1;
return 0;
}
void in_mt()
{
for(int i=0;i<17;i++)
{
for(int j=0;j<19;j++)
{
cout<<b[i][j];
}
cout<<endl;
}
}
int main()
{
f=fopen("inp.txt","r");
for(int i=0;i<17;i++)
{
for(int j=0;j<19;j++)
{
fscanf(f,"%d",&a[i][j]);
}
}
for(int i=0;i<17;i++)
{
for(int j=0;j<19;j++)
{
b[i][j]=0;
}
}
in_mt();
for(int i=0;i<17;i++)
{
for(int j=0;j<19;j++)
{
khanang(i,j);
}
}
cout<<endl<<endl<<endl;
timduong(0,0);
in_mt();
fclose(f);
}
Bài liên quan
Yêu cầu của đề là gì ?
Bạn đặt dk gì để đệ quy không đi vòng tròn quay lại theo ô cũ (lặp vô hạn nên bị lỗi).
Dạ cái ma trận b ấy a để ý nếu có 1 điểm được đi qua thì tại đó b(i,j) giảm đi 1 nếu b(i,j) bằng 0 thì sẽ ko thể đi quay lại điểm đó nữa
không liên quan cơ mà bài này quen quen ông học cấu trúc dữ liệu và giải thuật lớp tôi à?
Chắc vậy bài này tôi bảo vệ xong rồi nhưng nghĩ cách tối ưu thuật toán thôi