Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <fstream>
- using namespace std;
- int arr[100];
- int x,n;
- int dp[1000][1000];
- char niz[1000][1000];
- int dfs(int i,int j){
- if (i==n-1 and j==n-1){
- return 1;
- }
- if (dp[i][j]!=-1){
- return dp[i][j];
- }
- int sum=0;
- if (i+1<n and niz[i+1][j]!='*'){ // down
- sum=sum+dfs(i+1,j);
- }
- if (j+1<n and niz[i][j+1]!='*'){ // right
- sum=sum+dfs(i,j+1);
- }
- dp[i][j]=sum%(int)(1e9+7);
- return sum%(int)(1e9+7);
- }
- int main(){
- cin>>n;
- for (int i=0;i<n;i++){
- for (int j=0;j<n;j++){
- cin>>niz[i][j];
- }
- }
- for (int i=0;i<1000;i++){
- for (int j=0;j<1000;j++){
- dp[i][j]=-1;
- }
- }
- if (niz[0][0]=='*'){
- cout<<0;
- }
- else{
- cout<<dfs(0,0);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment