[UVa] 1600 - Patrol Robot

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1600 - Patrol Robot
Source            : UVa Online Judge
Category          : Backtrack with Pruning
Algorithm         : Backtrack with Pruning
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define inf                123456
 
static const int maxn = 22;
 
int dr[] = {+0, +0, +1, -1};
int dc[] = {+1, -1, +0, +0};
 
int row, column, k;
int obstackle[maxn][maxn];
bool vis[maxn][maxn];
int minlen;
 
bool go(int r, int c)
{
    return r >= 1 && r <= row && c >= 1 && c <= column;
}
 
void dfs(int x, int y, int tobstacle, int level)
{
    if (tobstacle > k) return;
    if (x == row && y == column)
    {
        minlen = level;  // updating search limit
        return;
    }
    // length of the best possible path from current state
    int bestfromhere = abs(row-x) + abs(column-y);
    // Pruning paths which will never give optimal answer
    if (level + bestfromhere >= minlen) return;
    for (int i = 0; i < 4; i++)
    {
        int r = x + dr[i];
        int c = y + dc[i];
        if (!go(r, c) || vis[r][c]) continue;
        vis[r][c] = 1;
        if (obstackle[r][c]) dfs(r, c, tobstacle+1, level+1);
        else dfs(r, c, 0, level+1);
        vis[r][c] = 0; // Backtrack
    }
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        cin >> row >> column >> k;
        for (int i = 1; i <= row; i++)
            for (int j = 1; j <= column; j++)
                cin >> obstackle[i][j];
        minlen = inf;
        vis[1][1] = 1;
        dfs(1, 1, 0, 0);
        if (minlen == inf) cout << "-1\n";
        else cout << minlen << endl;
        memset(vis, 0, sizeof vis);
        memset(obstackle, 0, sizeof obstackle);
    }
}