// Arup Guha
// 4/25/2024
// Solution to Spring 2024 COP 3502H Final Exam Question 6

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DEBUG 1

int treasure(char** map, int n, int r, int c);

int main(void) {

    srand(time(0));

    // Read in map.
    char** map;
    int n;
    scanf("%d", &n);
    map = calloc(n, sizeof(char*));
    for (int i=0; i<n; i++) {
        map[i] = calloc(n+1, sizeof(char));
        scanf("%s", map[i]);
    }

    // Run it.
    int score = treasure(map, n, 0, 0);
    printf("Score is %d\n", score);

    // Free stuff.
    for (int i=0; i<n; i++)
        free(map[i]);
    free(map);

    return 0;
}

// Sorry, this would be way shorter if I wrote the problem differently. There's probably a shorter way to do this, but I just
// wanted to make sure this solution is accurate to what was written on the test.'
int treasure(char** map, int n, int r, int c) {

    if (DEBUG) printf("go to %d %d\n", r, c);

    // Safe to do this first due to pre-req.
    int score = 0;
    if (map[r][c] == 'T')
        score = 1;

    // I check last row first. There are two cases here, we're stuck or must go to the right.
    if (r == n-1) {
        if (c == n-1 || map[r][c+1] == '*') return score;
        return score + treasure(map, n, r, c+1);
    }

    // Then last column. Either we're stuck or must go down.
    if (c == n-1) {
        if (map[r+1][c] == '*') return score;
        return score + treasure(map, n, r+1, c);
    }

    // Only other way we could be stuck.
    if (map[r+1][c] == '*' && map[r][c+1] == '*') return score;

    // Now check if one position is blocked so that we have to go the other way.
    if (map[r+1][c] == '*') return score + treasure(map, n, r, c+1);
    if (map[r][c+1] == '*') return score + treasure(map, n, r+1, c);

    // Finally we get a choice!
    if (rand()%2 == 0)
        return score + treasure(map, n, r+1, c);
    return score + treasure(map, n, r, c+1);
}