There is a cleaning robot which is cleaning a rectangular grid of size Nx M, represented by array R consisting of N strings. Rows are numbered from 0 to N-1 (from top to bottom) and columns are numbered from 0 to M-1 (from left to right).

The robot starts cleaning in the top-left corner, facing rightwards. It moves in a straight line for as long as it can, i.e. while there is an unoccupied grid square ahead of it. When it cannot move forward, it rotates 90 degrees clockwise and tries to move forward again until it encounters another obstacle, and so on. Dots in the array (".") represent empty squares and "X"s represent occupied squares (ones the robot cannot move through). Each square that the robot occupied at least once is considered clean. The robot moves indefinitely.

Write a function: int solution (vector<string> &R); that, given an array R consisting of N strings, each of length M, representing the grid, returns the number of clean squares.

Examples:

Solution:

#include <iostream>
#include <vector>
#include <functional>

using namespace std;

int solution(std::vector<std::string>& R) {
    const int n = R.size();
    const int m = R[0].size();
    int cnt = 0;
    vector<vector<vector<bool>>> visit(n, vector<vector<bool>>(m, vector<bool>(4, false)));
    static const vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    function<void(int, int, int)> dfs = [&](int i, int j, int d) {
        if (visit[i][j][d]) {
            return;
        }

        cnt += (R[i][j] == '.');
        visit[i][j][d] = true;
        R[i][j] = '-';
    
        auto can_move = [&](int i, int j) -> bool {
            return i >= 0 && i < n && j >= 0 && j < m && R[i][j] != 'X';
        };
        
        
        auto new_i = i + dirs[d][0];
        auto new_j = j + dirs[d][1];

        if (can_move(new_i, new_j)) {
            dfs(new_i, new_j, d);
        } else {
            dfs(i, j, (d + 1) % 4);
        }
    };

    dfs(0, 0, 0);
    return cnt;
}

int main()
{
    vector<string> test1 = {"...X..", "....XX", "..X..."};
    vector<string> test2 = {"....X..", "X......", ".....X.", "......."};
    vector<string> test3 = {"...X.", ".X..X", "X...X", "..X.."};
    vector<string> test4 = {"."};
    
    auto validate = [](int test, int cnt, int expected) {
        std::cout << "Test " << test << ": ";
        if (cnt == expected) {
            std::cout << "PASSED" << std::endl;
        } else {
            std::cout << "FAILED -- expected " << expected << " vs actual: " << cnt << endl;
        }
    };

    validate(1, solution(test1), 6);
    validate(2, solution(test2), 15);
    validate(3, solution(test3), 9);
    validate(4, solution(test4), 1);

    return 0;
}