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);
}
Gió viết 22:12 ngày 30/09/2018

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).

Trần Tuấn An viết 22:02 ngày 30/09/2018

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

Chiến Minh Nguyễn viết 21:59 ngày 30/09/2018

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 à?

Trần Tuấn An viết 22:03 ngày 30/09/2018

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

Bài liên quan
0