depth first search recursion in matrix

Question

http://codeforces.com/contest/540/problem/C

This problem is solved using depth first recursion on matrix and i got this code for the problem. Can anyone explain why/where recursion is working on this matrix?

#include <bits/stdc++.h>
using namespace std;
int a, b, used[600][600];
char c;
void dfs( int x, int y )
{
    used[x][y]++;
    if( used[x][y] >= 3 || x < 1 || y < 1 || x > a || y > b )
        return;
    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
}
int main()
{
    int i, j;
    cin >> a >> b;
    for( i = 1; i <= a; i++ ){
        for( j = 1; j <= b; j++ ){
            cin >> c;
            if( c == '.' )    used[i][j] = 1;
            else used[i][j] = 2;
         }
     } 
     int x1, y1, x2, y2;
     cin >> x1 >> y1 >> x2 >> y2;
     used[x1][y1] = 1;
     dfs(x1, y1);
     if( used[x2][y2] >= 3 )    cout << "YES";
     else cout << "NO";
}

Gaurav Jain Gaurav Jain · Accepted Answer · 2017-01-08T07:23:46

This problem can be thought of as a graph with edges connecting cells(nodes) which are adjacent i.e. share a boundary.

When DFS is implemented using a stack structure it is easier to see recursion. Here recursion is implemented in the form of function calls. We would call dfs for only those nodes which are:

directly reachable from the current node we are examining(which are all the cells 
adjacent to (x, y)).

Call to dfs(x, y); results in calling dfs(x + i, y + j); for (i, j) = {(-1, 0), (0, 1), (1, 0), (0, -1)}. As a consequence, the progam status word(variables, instruction pointer etc.) at the time dfs(x + 1, y) is called, is pushed implicitly onto the stack memory used by the program. These calls result in increasing the count of cells adjacent to (x, y) by 1.

Recursion unfolds when if( used[x][y] >= 3 || x < 1 || y < 1 || x > a || y > b )

condition is met resulting in return to coordinates(node) which called dfs on (x, y) OR when all the calls to dfs(x + i, y + j) for (i, j) = {(-1, 0), (0, 1), (1, 0), (0, -1)} have returned control to dfs(x, y) i.e. the after the line dfs(x, y - 1).

So recursion is all around when you are calling dfs(x -1, y), dfs(x, y -1) etc. within dfs(x, y);

depth first search recursion in matrix

1 Answers