//#include <stdbool.h>
//#include <stdio.h>

int N_ROWS, N_COLS;

char maze[4][5];

bool isValid(int r, int c) {

    return (r >= 0 && r < N_ROWS && c >= 0 && c < N_COLS && maze[r][c] != '#' && maze[r][c] != 'V');

}

bool findPathDFS(int r, int c) {

    if (maze[r][c] == 'F') { 

        return true;

    }

    maze[r][c] = 'V';

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1}; 

    for (int i = 0; i < 4; i++) {

        int next_r = r + dr[i];
        int next_c = c + dc[i];

        if (isValid(next_r, next_c)) {

            if (findPathDFS(next_r, next_c)) {

                return true;

            }

        }

    }

    maze[r][c] = '.'; 
    return false;

}

void setup() {

    Serial.begin(9600);

    N_ROWS = 4;
    N_COLS = 5;
    
    char example_maze[4][5] = {

        {'.', '.', '.', '.', 'S'},
        {'.', '.', '#', '#', '#'},
        {'.', '.', '.', '#', '#'},
        {'.', '#', 'F', '#', '.'}

    };

    for (int i = 0; i < N_ROWS; i++) {
    	
        for (int j = 0; j < N_COLS; j++) {
        	
            maze[i][j] = example_maze[i][j];
            
        }
        
    }

    int start_r = 0, start_c = 4;

    if (findPathDFS(start_r, start_c)) {
        Serial.println("Path exists!\n");
    } else {
        Serial.println("No path found.\n");
    }

}

void loop() {
  // put your main code here, to run repeatedly:

}