写在开头：非官方题解，加上比较菜，说错的地方还望指正。

1.理思路：去 是最短路径，最短路径肯定也是简单路径，不然进了死胡同再出来浪费步数啊。回来题目也说了是简单路径，并且从左上到右下，和从右下到左上其实一个意思。 所以该题本质是在求 “从左上到右下的所有简单路径中，最短的那条，和路上项链最多的那条”。

2.选做法：求两点的简单路径，我个人选的DFS，不过BFS好像也没毛病，至于BFS+DFS跑两遍的做法我觉得跑多了。

3.测试点注意：a.左上角即出发位置的脚下有项链。

4.参考源码（不知道该不该有，自己的写法可能不正统）

#include <cstdio>
#include <iostream>
#include <cstring> 
using namespace std;
char c[105][105];
int n,m;
int p,xi;
int jp,jx;
int xy[4][2]={1,0,0,1,-1,0,0,-1};
void DFS(int x,int y,int xi,int p)
{
    if(x==n&&y==m)
    {
        if(p<jp)
            jp=p;
        if(xi>jx)
            jx=xi;
        return; 
    }
    for(int i=0;i<4;i++)
    {
        int xx=x+xy[i][0],yy=y+xy[i][1];
        if(c[xx][yy]=='0'||c[xx][yy]=='#')
        {
            bool f=false;
            if(c[xx][yy]=='#')
            {       
                xi++;
                f=true;
            }
            p++;
            c[xx][yy]='1';
            DFS(xx,yy,xi,p);
            xi=f?xi-1:xi;
            c[xx][yy]=f?'#':'0';
            p--;        
        }
    }
}
int main()
{
    jp=99999;
    jx=0;
    memset(c,'1',sizeof(c));
    scanf("%d%d",&n,&m);
    getchar();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            c[i][j]=getchar();
        getchar();
    }
    bool f=false;
    if(c[1][1]=='#')
        f=true;
    c[1][1]='1';
    if(f) DFS(1,1,1,0);
    else  DFS(1,1,0,0);
    cout<<jp<<' '<<jx<<endl;
    return 0;
}

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
int n,m;
char G[maxn][maxn];
int vis[maxn][maxn];
int ans1=INF;
int ans2=0;
bool check(int x,int y) {
    if(x<=0||x>=(n+1)||y<=0||y>=(m+1)||(G[x][y]=='1')) return false;
    return true;
}
void dfs(int x,int y,int len){
    if(x==n&&y==m){
        ans1=min(ans1,len);
        return;
    }
    if(len>=ans1) return;
    for(int i=0;i<=3;i++){
        int newx=x+dx[i];
        int newy=y+dy[i];
        if(check(newx,newy)&&!vis[newx][newy]){
            vis[newx][newy]=1;
            dfs(newx,newy,len+1);
            vis[newx][newy]=0;
        }
    }
}
void rdfs(int x,int y,int len){
    if(G[x][y]=='#'){
         len++;
         //cout<<x<<" "<<y<<endl;
         
    }
    if(x==1&&y==1){
        ans2=max(len,ans2);
        return;
    }
    for(int i=0;i<=3;i++){
        int newx=x+dx[i];
        int newy=y+dy[i];
        if(check(newx,newy)&&vis[newx][newy]==0){
            vis[newx][newy]++;
            //if(G[newx][newy]=='#') rdfs(newx,newy,len+1);
            //else 
            rdfs(newx,newy,len);
            vis[newx][newy]--;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    freopen("营救公主.in","r",stdin);
    memset(vis,0,sizeof(vis));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>G[i][j];
        }
    }
    vis[1][1]=1;
    dfs(1,1,0);
    cout<<ans1<<" ";
    memset(vis,0,sizeof(vis));
    vis[n][m]=1;
    rdfs(n,m,0);
    /*
    cout<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<G[i][j];
        }
        cout<<endl;
    }
    */
    cout<<ans2;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif