时空限制：1000ms，256MB

样例：

输入

5 5
*..*.
.*..*
.....
*....
*****

输出

4 7

求调的代码：（只用第二个，就是比较正常的那个bfs即可）

#include<bits/stdc++.h>
using namespace std;
const int N=2100;
struct node{
    int x,y;
};
int dis1[N][N],dis2[N][N];
char mp[N][N];
int n,m;
int dx[2]={1,0};
int dy[2]={0,1};
int dir(int x,int y){
    //0:down&&1:right&&2:不变
    if(x==n) return 1;
    if(y==m) return 0;
    int d1=0,d2=0;
    for(;x+d1<=n;d1++){//列
        if(mp[x+d1][y]=='*') break;
    }
    for(;y+d2<=m;d2++){//行
        if(mp[x][y+d2]=='*') break;
    }
    if(x+d1==n+1&&y+d2==m+1) return (d1==d2?2:(d1>d2?0:1));
    else if(x+d1==n+1) return 1;
    else if(y+d2==m+2) return 0;
    else{
        if(d1>d2) return 1;
        else if(d1<d2) return 0;
        else return 2;
    }
}
void _bfs(){//明
    queue<node> q;
    bool dire=0;//0:down,1:right
    q.push({1,1});
    if(mp[1][1]=='*') dis1[1][1]=1;
    while(!q.empty()){
        node n1=q.front();
        q.pop();
        int di=dir(n1.x,n1.y);
        int tx,ty;
        if(di==1) dire=1,tx=n1.x,ty=n1.y+1;
        else if(di==0) dire=0,tx=n1.x+1,ty=n1.y;
        else tx=n1.x+dx[dire],ty=n1.y+dy[dire];
        dis1[tx][ty]=dis1[n1.x][n1.y];
        if(mp[tx][ty]=='*'){
            dis1[tx][ty]++;
            mp[tx][ty]='.';
        }
        q.push({tx,ty});
        if(tx==n&&ty==m) return;
    }
}
void print(){
    for(int i=1;i<=n;i++){
            cout<<endl;
        for(int j=1;j<=m;j++){
            cout<<dis2[i][j]<<" ";
        }
    }
    cout<<endl;
}
void bfs(){//最优
    queue<node> q;
    q.push({1,1});
 //   if(mp[1][1]=='*') dis2[1][1]=1;
    while(!q.empty()){
        node no=q.front();
        q.pop();
        for(int i=0;i<2;i++){
            int tx=no.x+dx[i];
            int ty=no.y+dy[i];
            if(mp[tx][ty]=='*'||mp[tx][ty]=='.'){
                q.push({tx,ty});
                dis2[tx][ty]=max(dis2[tx][ty],dis2[no.x][no.y]+(mp[tx][ty]=='*'?1:0));
            }
        }
//        print();
    }
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
//    freopen("chess.in","r",stdin);
//    freopen("chess.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            if(mp[i][j]=='*') dis2[i][j]=1;
        }
    }
    _bfs(),bfs();
    cout<<dis1[n][m]<<" "<<dis2[n][m];
//    print();
    return 0;
}

thx大佬