Codeforces1214 D Treasure Island

#include <bits/stdc++.h>
using namespace std;
const int maxn =  1000005;
int dir[2][2] = {1,0,0,1};
int s,t;
char mp[maxn];
int n,m,vis[maxn];
int ans;
void dfs(int id){
	if(ans)return ;
	if(id==t){
		ans++;return;
	}
	int y = id%m, x = id/m;
	for(int i=0;i<=1;i++){
		int tx = x+dir[i][0];
		int ty = y+dir[i][1];
		if(tx>=n||ty>=m||vis[tx*m+ty])continue;
		vis[tx*m+ty] = 1;
		dfs(tx*m+ty); 
		if(ans)return;
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%s",mp+i*m);
		for(int j=i*m;j<(i+1)*m;j++){
			if(mp[j]=='#')vis[j] = 1;
		}
	}
	s = 0,t = n*m-1;
	vis[s] = 1;	vis[t] = 0;
	dfs(s);
	if(!ans){
		printf("0\n");
		return 0;
	}
	vis[s] = 1;	vis[t] = 0;
	ans = 0;
	dfs(s);
	if(ans){
		printf("2\n");
	}else printf("1\n");
	return 0;
}