/CF - 1214D.cpp Secret
Created
November 28, 2020 12:14
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<bits/stdc++.h> | |
#define Input freopen("in.txt","r",stdin) | |
#define Output freopen("out.txt","w",stdout) | |
#define ll long long int | |
#define ull unsigned long long int | |
#define pii pair<int,int> | |
#define pll pair<ll,ll> | |
#define sc scanf | |
#define scin(x) sc("%d",&(x)) | |
#define scin2(x,y) sc("%d %d",&(x),&(y)) | |
#define scln(x) sc("%lld",&(x)) | |
#define scln2(x,y) sc("%lld %lld",&(x),&(y)) | |
#define pf printf | |
#define ms(a,b) memset(a,b,sizeof(a)) | |
#define pb(a) push_back(a) | |
#define RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++) | |
using namespace std; | |
/** Problem Summary: Find number of non-overlapping path from source to destination **/ | |
const int fx[] = {+1,+0}; | |
const int fy[] = {+0,+1}; | |
int n,m; | |
vector<vector<int> >vis; | |
vector<vector<char> >grid; | |
bool DFS(int sx,int sy) | |
{ | |
if(sx==n-1 && sy==m-1) | |
return 1; | |
int ret = 0; | |
vis[sx][sy] = 1; | |
for(int k=0 ; k<2 ; k++){ | |
int nx = sx+fx[k]; | |
int ny = sy+fy[k]; | |
if(nx>=0 && nx<n && ny>=0 && ny<m && grid[nx][ny]=='.' && !vis[nx][ny]){ | |
ret |= DFS(nx , ny); | |
} | |
if(ret) | |
break; | |
} | |
return ret; | |
} | |
void Solve(int t) | |
{ | |
int i,j,k,path=0; | |
cin>>n>>m; | |
for(i=1 ; i<=n ; i++){ | |
vector<char>temp; | |
vector<int>temp2; | |
char ch; | |
for(j=1 ; j<=m ; j++){ | |
cin>>ch; | |
temp.pb(ch); | |
temp2.pb(0); | |
} | |
temp2.pb(0); | |
grid.pb(temp); | |
vis.pb(temp2); | |
} | |
path += DFS(0 , 0); | |
vis[0][0] = vis[n-1][m-1] = 0; | |
path += DFS(0 , 0); | |
cout<<path<<endl; | |
} | |
int main() | |
{ | |
int t,T; | |
T = 1; | |
RUN_CASE(t,T) | |
{ | |
Solve(t); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment