שלום,

אני אשמח אם תוכלו לעזור לי לפתור את תרגיל 3 מהמבחן הנ"ל:

http://www.cs.biu.ac.il/~kalechm/c_04/recursive7_math.pdf

אני הצלחתי לעשות שהפונקציה תמנה את הדרכים אם הצעדים היו רק ימינה ולמטה. הבעיה היא שכאשר אני מנסה לאפשר גם צעדים למעלה ושמאלה הפונקציה נכנסת ללולאה אינסופית כי היא עוברת לתא הבא אבל אז חוזרת לתא הקודם וכך הלאה.

זאת הפונקציה שכתבתי ונכנסת ללולאה אינסופית:

int CountPaths(matrix mat, const int SIZE, int x, int y)
{
  //cout << "[" << x << "][" << y << "]\n";

  if ( (x<0||x>=SIZE) || (y<0||y>=SIZE)) //if not in matrix bounds
    return 0;
  if (x==SIZE-1&&y==SIZE-1) //if is the end of the matrix
    return 1;
  if (mat[x][y]==-1) //if can't move to this cell
    return 0;

  int sum = 0;
  sum += CountPaths(mat,SIZE,x+1,y);
  sum += CountPaths(mat,SIZE,x-1,y);
  sum += CountPaths(mat,SIZE,x,y+1);
  sum += CountPaths(mat,SIZE,x,y-1);

  return sum;
}

עריכה:

ניסיתי להוסיף משתנה שיאמר לפונקציה מה היה התא קודם כדי שהיא לא תחזור אליו אך בכל זאת הפונקציה נכנסת ללולאה אינסופית.

זה הקוד:

int CountPaths(matrix mat, const int SIZE, int x, int y, short cameFrom)
{
  cout << "[" << x << "][" << y << "]\n";
  if ( (x<0||x>=SIZE) || (y<0||y>=SIZE)) //if not in matrix bounds
    return 0;
  if (x==SIZE-1&&y==SIZE-1) //if is the end of the matrix
    return 1;
  if (mat[x][y]==-1) //if can't move to this cell
    return 0;

  int sum = 0;
  if (cameFrom!=2)
    sum += CountPaths(mat,SIZE,x+1,y,1);
  if (cameFrom!=1)
    sum += CountPaths(mat,SIZE,x-1,y,2);
  if (cameFrom!=4)
    sum += CountPaths(mat,SIZE,x,y+1,3);
  if (cameFrom!=3)
    sum += CountPaths(mat,SIZE,x,y-1,4);

  return sum;
}

למרות משתנה העזר שהוספת עדיין יכולה להתקיים לולאה אינסופית במקרה של קיום מסלול מעגלי אפשרי, למשל עבור קטע המסלול

3 4 5

5 1- 7

2 9 1

גם אם אתה שואל מהיכן הגיע הצעד הקודם, אין מניעה שהאלגוריתם ירוץ מסביב ל 1- אינסוף פעמים.

יש אפשרות אחרת, והיא לסמן את המקום פשוט ב 1- כמקום לא חוקי אחרי שכבר צעדת עליו, ובסיום הפונקציה, להשיב את ערך המקום לערכו המקורי.

לא ראיתי גם היכן התייחסת לספירת מספר המסלולים האפשריים, וחישוב המסלול המינימלי בפונק' שכתבת.

אם תרצה, הנה הצעה לפתרון:

#include<stdio.h>
#include<limits.h>

#define N 5

bool InBound(int i, int j, int ArrSize);
int rec_short_path(int i, int j, int arr[N][N], int length,int& NumOfPathes);
int min(int a, int b, int c, int d);

int main(){
	int arr[N][N]={\
	{ 3, 1, 2, 4, 8},\
	{ 3,-1,20,-1, 4},\
	{ 5,-1,21,-1, 2},\
	{ 6,-1,25,-1, 1},\
	{ 1,-1, 3, 4, 1}};
	int NumOfPathes=0;
	int MinRoute=rec_short_path(0,0,arr,0,NumOfPathes);
	printf("shortest path: %d Number of Pathes: %d", MinRoute, NumOfPathes);
}


bool InBound(int i, int j, int ArrSize){
	if ((i<0)||(j<0)||(i>=ArrSize)||(j>=ArrSize))
		return false;
	return true;
}

int min(int a, int b, int c, int d){
	if (a==-1) a=INT_MAX;
	if (b==-1) b=INT_MAX;
	if (c==-1) c=INT_MAX;
	if (d==-1) d=INT_MAX;
	int m1= a<b ? a : b;
	int m2= c<d ? c : d;
	return (m1<m2 ? m1 : m2);
}


int rec_short_path(int i, int j, int arr[N][N], int length,int& NumOfPathes){
	if ((i==N-1)&&(j==N-1)){
		NumOfPathes++;
		return length+arr[i][j];
	}
	if (arr[i][j]==-1)
		return -1;

	int CurrCell=arr[i][j], res1=-1, res2=-1, res3=-1, res4=-1;
	arr[i][j]=-1;
	if (InBound(i+1,j,N))		
		res1=rec_short_path(i+1 ,j ,arr , length+CurrCell,NumOfPathes);
	if (InBound(i-1,j,N))
		res2=rec_short_path(i-1,j,arr, length+CurrCell,NumOfPathes);
	if (InBound(i,j+1,N))
		res3=rec_short_path(i,j+1,arr, length+CurrCell,NumOfPathes);
	if (InBound(i,j-1,N))
		res4=rec_short_path(i,j-1,arr, length+CurrCell,NumOfPathes);

	arr[i][j]=CurrCell;
	if ((res1==-1)&&(res2==-1)&&(res3==-1)&&(res4==-1))
		return -1;
	else
		return min(res1,res2,res3,res4);
}