Helpful Currents

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll MOD = 1000003;
const ll M = 55555;
const ll N = 333;

char grid[N][M];
int n ,m ,c;
ll dp[N][M];

inline bool isValid(int i ,int j)
{
    return (0 <= i && i < n && 0 <= j && j < m && grid[i][j] != '#');
}

bool DFS(int i ,int j)
{
    /// --- Check if there is path --- ///
    if( !isValid(i ,j) ) return false;
    if( grid[i][j] == '@' ) return true;

    dp[i][j] = true;

    bool re = false;

    if( !dp[i - 1][j] ){
        re |= DFS(i - 1 ,j);
    }

    if( grid[i][j] == '<' ){
        if( !dp[i][j - 1] ){
            re |= DFS(i ,j - 1);
        }
    }

    if( grid[i][j] == '>' ){
        if( !dp[i][j + 1] ){
            re |= DFS(i ,j + 1);
        }
    }

    return re;
}

ll calc(int i ,int j)
{
    if( !isValid(i ,j) )    return 0ll;
    if( grid[i][j] == '@' ) return 1ll;

    ll &re = dp[i][j];
    if( re + 1 ) return re;

    re = calc(i - 1 ,j);
    re %= MOD;

    if( grid[i][j] == '<' ){
        re += calc(i ,j - 1);
        re %= MOD;
    }

    if( grid[i][j] == '>' ){
        re += calc(i ,j + 1);
        re %= MOD;
    }

    return re;
}

int main()
{
    scanf("%d%d%d" ,&n ,&m ,&c);
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            scanf("\n%c" ,&grid[i][j]);
        }
    }

    memset(dp ,0 ,sizeof dp);
    if( DFS(n - 1 ,c) ){
        memset(dp ,-1 ,sizeof dp);
        printf("%lld" ,calc(n - 1 ,c));
    } else {
        puts("begin repairs");
    }

    return 0;
}