# 14042 - Capybara Hunts All!
https://acm.cs.nthu.edu.tw/problem/14042/

[toc]

---

## Depth First Search Solution

### 1. Determining the Recursion Movement

Assume you are in position (x, y). You can go to 4 directions:
* (x+1, y)
* (x-1, y)
* (x, y+1)
* (x, y-1)

Which in recursion will be:

char arr[500][500]; // The map in the array

void dfs(int x, int y){
    dfs(x+1, y);
    dfs(x-1, y);
    dfs(x, y+1);
    dfs(x, y-1);
    
    return;
}

However there are some problems here:
1. Let assume Capybara starts from (10, 10) Capybara can go to (10, 11). However when capybara at (10, 11), he can go back to (10, 10). So **there will be a repitition** and it will be looping forever.
2. He can go everywhere, even go to walls!
3. What if he go outside from the map?

### 2. Set the Boundaries
As we go to coordinate (x, y) that's invalid, we can easily return from the function.

int n, m;
char arr[500][500]; // The map in the array
int visited[500][500]; // The coordinate if it's visited

void dfs(int x, int y){
    // If Capybara go to somewhere out of array range, then it's invalid
    if(x < 0 || y < 0 || x >= n || y >= m){
        return;
    }
    
    // If it's a wall, then it's invalid
    if(arr[x][y] == '#'){
        return;
    }
    
    // If the location has been visited, then we will return
    // else we will mark this (x, y) as visited, so we will not go here again
    if(visited[x][y] == 1){
        return;
    }
    else{
        visited[x][y] = 1;
    }
    
    dfs(x+1, y);
    dfs(x-1, y);
    dfs(x, y+1);
    dfs(x, y-1);
    
    return;
}

### 3. Calculate the step
Everytime we make a movement, the step count will be increase by 1. We can solve this problem by add parameter in the function.

int n, m;
char arr[500][500]; 
int visited[500][500];

void dfs(int x, int y, int step){ // add variable step
    if(x < 0 || y < 0 || x >= n || y >= m){
        return;
    }
    if(arr[x][y] == '#'){
        return;
    }
    if(visited[x][y] == 1){
        return;
    }
    else{
        visited[x][y] = 1;
    }
    
    dfs(x+1, y, step+1); // every movement we add 1 step
    dfs(x-1, y, step+1);
    dfs(x, y+1, step+1);
    dfs(x, y-1, step+1);
    
    return;
}

### 4. Calculate the Solution

If we reach to 'M' with *n* step, then step to returning to his tent is also *n*. Therefore everytime we find 'M', we can add our solution by **2 * step**.

> *Note :*
> *As the explanation give "There is only 1 path from (a, b) to (c, d)" if there is no overlapping path, We don't need to worry if there is other path with different step being add to solution*

int sol = 0; // Declare the solution as global variable
int n, m;
char arr[500][500]; 
int visited[500][500];

void dfs(int x, int y, int step){ 
    if(x < 0 || y < 0 || x >= n || y >= m){
        return;
    }
    if(arr[x][y] == '#'){
        return;
    }
    if(visited[x][y] == 1){
        return;
    }
    else{
        visited[x][y] = 1;
    }
    
    // If it's meat ,
    if(arr[x][y] == 'M'){
        sol += 2*step; // add the answer by 2*step if we find 'M'
    }
    
    dfs(x+1, y, step+1);
    dfs(x-1, y, step+1);
    dfs(x, y+1, step+1);
    dfs(x, y-1, step+1);
    
    return;
}

### 5. Final Touch!

The backtracking seems complete! We just need to make the main function!

#include <stdio.h> 

int sol = 0;
int n, m;
char arr[500][500]; 
int visited[500][500];

void dfs(int x, int y, int step){ 
    if(x < 0 || y < 0 || x >= n || y >= m){
        return;
    }
    if(arr[x][y] == '#'){
        return;
    }
    if(visited[x][y] == 1){
        return;
    }
    else{
        visited[x][y] = 1;
    }
    
    if(arr[x][y] == 'M'){
        sol += 2*step; 
    }
    
    dfs(x+1, y, step+1);
    dfs(x-1, y, step+1);
    dfs(x, y+1, step+1);
    dfs(x, y-1, step+1);
    
    return;
}

int main(){
    int start_x, start_y; 
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf(" %c", &arr[i][j]);
            if(arr[i][j] == 'S'){ // We start from S,
                start_x = i;      // We will record the initial position
                start_y = j;
            }
        }
    }
    
    dfs(start_x, start_y, 0); // Start from S with 0 step
    printf("%d\n", sol); // Print the solution
    
}

// by Aurick