# Smart Frog codechef problem solution by backtracking

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.

### 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; }

## Leave a Reply