FCF2P1 - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Pritish Priyatosh Nayak

Tester: Sibasish Ghosh

Editorialist: Pritish Priyatosh Nayak

DIFFICULTY:

Easy

PREREQUISITES:

Implementation

PROBLEM:

Given a N \times N matrix where each cell has a direction character. Upon arriving at a cell you can only head in the direction it’s pointing towards.
Do dfs from each of the cell of the top row and count the number of cells from which dfs ends at cells whose coordinates have even sum.

EXPLANATION:

It’s a standard dfs on matrix/grid problem.
Simply use recursion to perform the dfs.

Upon arriving at a cell (x,y),

  • if character is ‘D’ then go to cell (x+1,y) if possible
  • if character is ‘L’ then go to cell (x,y-1) if possible
  • if character is ‘R’ then go to cell (x,y+1) if possible

See the tester/setter solution for implementation.

SOLUTIONS:

Setter's/Editorialist's Solution 
    #include<bits/stdc++.h>
    #define int long long
    #define rep(i,x,y) for(int i=x;i<y;i++)
    #define repr(i,x,y) for(int i=x;i>=y;i--) 
    #define mod 1000000007
    using namespace std;
    char arr[2001][2001];
    int dp[2001][2001];
    int n;
     
    int recur(int x,int y)
    {
    	assert(x>=0&&x<n);
    	assert(y>=0&&y<n);
    	if(dp[x][y]!=-1)return dp[x][y];
      
      int X=x,Y=y;
    	if(arr[x][y]=='D')X++;
    	if(arr[x][y]=='L')Y--;
    	if(arr[x][y]=='R')Y++;
     
    	if(X<n&&Y<n&&X>=0&&Y>=0){
    		dp[x][y]=recur(X,Y);
    	}
    	else {
    		dp[x][y]=(x+y)%2;
    	}
    	return dp[x][y];
    }
    void Onigiri()
    {
      cin>>n;
     
      rep(i,0,n)
      	rep(j,0,n)
      	{cin>>arr[i][j];dp[i][j]=-1;}
     
      int ans=0;
      rep(i,0,n)
      {
      	if(recur(0,i)==0)ans++;
      }
      cout<<ans;
    }
    signed main()
    {
       ios_base::sync_with_stdio(false);cin.tie(NULL); 
       int t=1; 
       cin>>t;
     
       while(t--)
       {Onigiri();cout<<"\n";}
     
       cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
       return 0;
    }
Tester's Solution 
    #include<bits/stdc++.h>
    #define mod 1000000007
    #define F first
    #define S second
    #define pb push_back
    #define all(v) v.begin(),v.end()
    #define rall(v) v.rbegin(),v.rend()
     
    using namespace std;
    typedef long long int ll;
     
    ll n;
    char grid[1010][1010];
     
    bool check(ll x,ll y)
    {
        if(x < 1 || x > n || y < 1 || y > n)
            return false;
        return true;
    }
     
    bool dfs(ll x,ll y)
    {
        if(grid[x][y] == 'R')
        {
            if(!check(x,y+1))
                return ((x+y)%2 == 0);
            return dfs(x,y+1);
        }
        if(grid[x][y] == 'L')
        {
            if(!check(x,y-1))
                return ((x+y)%2 == 0);
            return dfs(x,y-1);
        }
        if(grid[x][y] == 'D')
        {
            if(!check(x+1,y))
                return ((x+y)%2 == 0);
            return dfs(x+1,y);
        }
    }
     
    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        ll t=1;
        cin>>t;
        while(t--)
        {
            ll i,j,ans=0;
            cin>>n;
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                    cin>>grid[i][j];
            }
            for(i=1;i<=n;i++)
            {
                if(dfs(1,i))
                    ans++;
            }
            cout<<ans<<"\n";
        }
        return 0;
    }
1 Like