dfs大法好==
写半天bfs疯狂MLE
dfs标记掉路上的一些点
然后再跑一遍dfs
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sc(x) scanf("%I64d",&x);
#define read(A) for(int i=0;i<n;i++)scanf("%I64d",&A[i]);
#define endl '\n'
#define fi first
#define se second
#define si signed
#define P pair<si,si>
#define pb push_back
#define maxn 1000000+100
bool A[maxn];
int n,m;
queue<P>q;
P fa[maxn];
bool vis[maxn];
int cnt=0;
bool bfs()
{
while(!q.empty())q.pop();
q.push(P(0,0));
while(!q.empty())
{
P a=q.front();
q.pop();
si x=a.fi;
si y=a.se;
//B[x*m+y]++;
if(x==n-1&&y==m-1)
{
// cnt++;
//f=0;
return false;
}
if(x+1<n)
{
if(A[(x+1)*m+y]==0)
{
fa[(x+1)*m+y]=P(x,y);
q.push(P(x+1,y));
}
}
if(y+1<m)
{
if(A[x*m+y+1]==0)
{
fa[x*m+y+1]=P(x,y);
q.push(P(x,y+1));
}
}
}
return true;
//else return false;
}
bool dfs(int x,int y)
{
vis[x*m+y]=1;
int a=x+1;
if(x==n-1&&y==m-1)return true;
if(a<n&&!vis[a*m+y]&&A[a*m+y]==0){
if(dfs(a,y))return true;
}
int b=y+1;
if(b<m&&!vis[x*m+b]&&A[x*m+b]==0){
if(dfs(x,b))return true;
}
return false;
}
signed main()
{
sc(n);
sc(m);
int t=0;
for(int i=0; i<n; i++)
{
getchar();
for(int j=0; j<m; j++)
{
A[i*m+j]=(getchar()=='#'?1:0);
t+=A[i*m+j];
}
}
if(t==0&&(n==1||m==1)){
cout<<1<<'\n';
return 0;
}
if(t==0)
{
cout<<2<<'\n';
return 0;
}
if(n==1||m==1){
cout<<0<<'\n';
return 0;
}
int ans=2;
if(!dfs(0,0)){
cout<<0<<'\n';
return 0;
}
vis[0]=vis[(n-1)*m+m-1]=0;
if(!dfs(0,0)){
cout<<1<<'\n';
return 0;
}
cout<<2<<'\n';
/* if(bfs())
{
cout<<0<<'\n';
return 0;
}
//cout<<B[1*m+2]<<endl;
P x=fa[(n-1)*m+m-1];
si c,d;
while(true){
c=x.fi,d=x.se;
if(c==0&&d==0)break;
x=fa[c*m+d];
A[c*m+d]=1;
}
if(bfs()){
cout<<1<<'\n';
return 0;
}
cout<<ans<<'\n';
*/
}