Backtracking problem is not easier to understand. For an average programmer practice is the only way to become an expert at backtracking problem solution. The article  “Smart Frog codechef problem solution by  backtracking” is one of the good problem to practice backtracking problem. The problem link  https://www.codechef.com/problems/G2.

Smart Frog codechef problem solution by backtracking

Problem description for Smart Frog codechef:

  • We need to find max number of cells that the smart frog can jump into.
  • Jump to the right to a cell in the same row, provided that the number written in that cell is not smaller than the number written in the current cell.
  • Jump downwards to a cell in the same column, provided that the number written in that cell is not greater than the number written in the current cell.
#include<iostream>
#include<algorithm>
using namespace std;

#define N 502
int mat[N][N];
int d[N][N];
int v[N][N];

bool canjumpinrow(int dx, int dy,int ii, int jj, int row, int col)
{
	if (dy > col )
		return false;
	// Jump to the right to any cell in the same row, provided that 
	 //the number written in thatcell is not smaller than the number written in the current cell.
	if (mat[dx][dy] >= mat[ii][jj] && !v[dx][dy])
	{
		return true;
	}
	return false;
}

bool canjumpincol(int dx, int dy ,int ii, int jj, int row, int col)
{
	if (dx > row )
		return false;
	// any cell in the same column, provided that the number written 
	//in thatcell is not greater than the number written in the current cell.
	if (mat[dx][dy] <= mat[ii][jj] && !v[dx][dy])
	{
		return true;
	}
	return false;
}

int visit(int ii, int jj, int row, int col)
{
	if (d[ii][jj] != -1)
		return d[ii][jj];

	if (ii > row || jj > col)
		return 0;

	int retr = 0;
	int retc = 0;

	v[ii][jj] = 1;

	// all possible 
	for (int p = jj + 1 ; p <= col; p++)
	{
		if (canjumpinrow(ii , p ,ii, jj, row, col))
		{
			retr =max(retr,1 + visit(ii, p, row, col));
		}
	}

	for (int p = ii + 1; p <= row; p++)
	{
		if (canjumpincol(p, jj,ii,jj, row, col))
		{
			retc =max(retc, 1 + visit(p, jj, row, col));
		}
	}
	v[ii][jj] = 0;

	return d[ii][jj] =  max(retr, retc);
}
int main()
{
	//freopen("input.txt", "r", stdin);

	int t = 0;
	cin >> t;
	for (int test = 0; test < t; test++)
	{
		int ans = 0;
		int row = 0;
		int col = 0;
		cin >> row >> col;

		for (int i = 1; i <= row; i++)
		{
			for (int j = 1; j <= col; j++)
			{
				cin >> mat[i][j];
				v[i][j] = 0;
				d[i][j] = -1;
			}

		}
		int max = 0;
		for (int i = 1; i <= row; i++)
		{
			for (int j = 1; j <= col; j++)
			{
				if (!v[i][j])
				{
					ans = visit(i, j, row, col);
					if (max == 0 || max < ans)
						max = ans;
				}
			
			}

		}

		cout << "Case #" << test + 1 << endl;
		cout << max + 1 <<endl;
	}

 



Related Contents to follow