Robot in a Grid

8.2 Robot in a Grid: Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are "off limits" such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.

• First I am going to try and solve this problem without the assumed constraint (of begin only able to move right down).

• My approach was to have the program follow a stack of operations that always have a priority.

• In particular, we know that moving towards the right and descending down will always allow us to get closer to our goal.

• However, there are situations where we get 'trapped'. The solution here is to just mark said node as not valid. We know this to happen when we're already tried going right or down. So we mark the visited node as 'n' for null, for elements we move left or down.

• O(2n) time, O(1) space

bool isValidCell(int row, int col, vector<vector<char>>& matrix) {
    return (row < matrix.size() && col < matrix.at(0).size() && row >= 0 && col >= 0
            && matrix.at(row).at(col) != 'n');
}


void traverseMatrix(vector<vector<char>>& matrix, int row, int col) {

    while (1) {
        cout << matrix.at(0).size() - 1 << " " << matrix.size() - 1 << endl;
        cout << row << " " << col << endl;

        // right
        if (isValidCell(row, col + 1, matrix)) {
            col += 1;
            matrix.at(row).at(col) = 'P';
            print2d(matrix);

            if (col == matrix.at(0).size() - 1 && row == matrix.size() - 1) break;
            continue;
        }


        // down
        if (isValidCell(row + 1, col, matrix)) {
            row += 1;
            matrix.at(row).at(col) = 'P';
            print2d(matrix);

            if (col == matrix.at(0).size() - 1 && row == matrix.size() - 1) break;
            continue;
        }


        // left
        if (isValidCell(row, col - 1, matrix)) {

            col -= 1;
            matrix.at(row).at(col) = 'P';
            matrix.at(row).at(col + 1) = 'n';
            print2d(matrix);

            if (col == matrix.at(0).size() - 1 && row == matrix.size() - 1) break;
            continue;
        }

        // up
        if (isValidCell(row - 1, col, matrix)) {

            row -= 1;
            matrix.at(row).at(col) = 'P';
            matrix.at(row + 1).at(col) = 'n';
            print2d(matrix);

            if (col == matrix.at(0).size() - 1 && row == matrix.size() - 1) break;
            continue;
        }
    }
}

int main()
{
    vector<vector<char>> matrix = {
        // 0   1   2   
        { '0','0','n' }, // 0
        { '0','n','0' }, // 1
        { '0','0','0' }, // 2
    }; // [8, 12]

    traverseMatrix(matrix, 0, 0);

     matrix = {
        // 0   1   2   3   4   5   6   7  
        { '0','0','0','0','0','0','0','n', }, // 0
        { '0','0','0','0','0','0','n','0', }, // 1
        { '0','0','0','0','0','n','0','0', }, // 2
        { '0','0','0','0','n','0','0','0', }, // 3
        { '0','0','0','n','0','0','0','0', }, // 4
        { '0','0','n','0','0','0','0','0', }, // 5 
        { '0','n','0','0','0','0','0','0', }, // 6
        { '0','0','0','0','0','0','0','0',  }, // 7
        { 'n','0','0','0','0','0','0','0', },  // 8
    }; // [8, 12]


    traverseMatrix(matrix, 0, 0);

    matrix = {
        // 0   1   2   3   4   5   6   7  
        { 'n','0','0','n','0','0','0','n', }, // 0
        { '0','n','0','0','0','0','0','0', }, // 1
        { '0','n','0','0','0','0','0','0', }, // 2
        { '0','0','0','0','0','0','0','0', }, // 3
        { '0','0','0','n','0','0','0','0', }, // 4
        { '0','n','n','0','n','0','n','0', }, // 5 
        { '0','n','0','0','0','n','n','n', }, // 6
        { '0','0','0','0','0','0','0','0', }, // 7
        { 'n','0','0','n','0','0','0','0', },  // 8
    }; // [8, 12]

    traverseMatrix(matrix, 0, 0);

}