UVa 11957 - Checkers Solution

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <stack>
#include <sstream>
#include <string>
using namespace std;
int n,si,sj;
vector<vector<int> > a,dp;
bitset<101> vis;
int m=1e6+7;
int dfs(int i,int j){
    if(i<0||i>=n||j>=n)
        return 0;
    if(i==0)
        return 1;
    if(dp[i][j])
        return dp[i][j]%m;
    int ans=0;
    if(i>0&&j<n-1&&a[i-1][j+1]){
        dp[i][j]+=dfs(i-1,j+1);
    }
    else{
        if(i>1&&j<n-2&&a[i-2][j+2])
            dp[i][j]+=dfs(i-2,j+2);
    }
    if(i>0&&j>0&&a[i-1][j-1])
        dp[i][j]+=dfs(i-1,j-1);
    else if(i>1&&j>1&&a[i-2][j-2])
        dp[i][j]+=dfs(i-2,j-2);
    return dp[i][j]%m;
}
int main(){
    int t,i=0;
    cin>>t;
    while(i++<t){
        cin>>n;
        vis.reset();
        a.assign(n,vector<int>(n,1));
        dp.assign(n,vector<int>(n));
        for(int i=0;i<n;i++){
            ws(cin);
            for(int j=0;j<n;j++){
                char c;
                cin>>c;
                if(c=='W'){
                    si=i,sj=j;
                }
                else if(c=='B'){
                    a[i][j]=0;
                }
            }
        }
        cout<<"Case "<<i<<": "<<(dfs(si,sj))%m<<endl;
    }
}