PROBLEM LINK:
Author: Pritish Priyatosh Nayak
Tester: Sibasish Ghosh
Editorialist: Pritish Priyatosh Nayak
DIFFICULTY:
Easy
PREREQUISITES:
Implementation, Dynamic programming
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:
The difference between the easy and hard version of this problem is in the constraints.
Bruteforce will time out in this problem. You need to use DP in this problem to memoize the recursion.
Create a N \times N sized dp table.
dp[i][j] denotes the parity of sum of coordinates of the destination cell that we reach if we continue dfs from (i,j).
Base case is when we cannot go to any other cell from current cell (i,j), and in such cases dp[i][j]=(i+j) \mod 2;
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;
}