70分TLE 悬赏2关

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1010;
struct tt{
    int x,y,d,cnt;
};
int n,m,mi[N][N][2],ma[N][N][2];
char a[N][N];
int dx[]={1,0};
int dy[]={0,1};
void bfs(){
    queue<tt> q;
    q.push({1,1,-1,0});
    mi[1][1][0]=0;
    mi[1][1][1]=0;
    ma[1][1][0]=0;
    ma[1][1][1]=0;
    while(!q.empty()){
        tt t=q.front();
        q.pop();
        if(t.x==n&&t.y==m){
            continue;
        }
        for(int i=0;i<2;i++){
            int sx=t.x+dx[i],sy=t.y+dy[i];
            if(sx>=1&&sx<=n&&sy>=1&&sy<=m&&a[sx][sy]!='#'){
                if(t.d==-1&&mi[sx][sy][i]>t.cnt){
                    mi[sx][sy][i]=t.cnt;
                    ma[sx][sy][i]=max(ma[sx][sy][i],t.cnt);
                    q.push({sx,sy,i,t.cnt});
                }
                else{
                    if(t.d!=i){
                        if(t.cnt+1<mi[sx][sy][i]){
                            mi[sx][sy][i]=t.cnt+1;
                            ma[sx][sy][i]=max(ma[sx][sy][i],t.cnt+1);
                            q.push({sx,sy,i,t.cnt+1});
                        }
                        else{
                            if(t.cnt+1>ma[sx][sy][i]){
                                ma[sx][sy][i]=t.cnt+1;
                                q.push({sx,sy,i,t.cnt+1});
                            }
                        }
                    }
                    else{
                        if(t.cnt<mi[sx][sy][i]){
                            mi[sx][sy][i]=t.cnt;
                            ma[sx][sy][i]=max(ma[sx][sy][i],t.cnt);
                            q.push({sx,sy,i,t.cnt});
                        }
                        else if(ma[sx][sy][i]<t.cnt){
                            ma[sx][sy][i]=t.cnt;
                            q.push({sx,sy,i,t.cnt});
                        }
                    }
                }
            }
        }
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            mi[i][j][0]=INT_MAX;
            mi[i][j][1]=INT_MAX;
            ma[i][j][0]=INT_MIN;
            ma[i][j][1]=INT_MIN;
        }
    }
    if(a[1][1]=='#'){
        cout<<-1;
        return 0;
    }
    bfs();
    if((ma[n][m][0]==INT_MIN&&ma[n][m][1]==INT_MIN)||(mi[n][m][0]==INT_MAX&&mi[n][m][1]==INT_MAX)){
        cout<<-1;
        return 0;
    }
    cout<<max(ma[n][m][0],ma[n][m][1])<<" "<<min(mi[n][m][0],mi[n][m][1]);
    return 0;
}