昨天学习了bfs的基本概念，今天来做一道经典习题练练手吧！ 

 bfs常用的两类题型

1.从A出发是否存在到达B的路径(dfs也可)

2.从A出发到B的最短路径（数小:<20才能用dfs） 

遗留的那个问题的答案-

题目：走迷宫 

 

#include <iostream>
using namespace std;int n;
const int N=1005;
int a[N][N];
typedef long long ll;
ll dp[N][N][2];void solve(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j][0]=-1;dp[i][j][1]=-1;}}dp[1][1][0]=a[1][1];dp[1][1][1]=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==1&&j==1)continue;if(a[i][j]==-1||(dp[i-1][j][0]==-1&&dp[i][j-1][0]==-1)){dp[i][j][0]=-1;dp[i][j][1]=-1;continue;}dp[i][j][0]=max(dp[i-1][j][0],dp[i][j-1][0])+a[i][j];ll c1=dp[i-1][j][0]/(i+j-2)*a[i][j];ll c2=dp[i][j-1][0]/(i+j-2)*a[i][j];ll m1=max(c1+dp[i-1][j][0],c2+dp[i][j-1][0]);ll m2=max(dp[i-1][j][1]+a[i][j],dp[i][j-1][1]+a[i][j]);dp[i][j][1]=max(m1,m2);}}cout<<max(dp[n][n][0],dp[n][n][1]);
} 
int main()
{// 请在此输入您的代码ios::sync_with_stdio(0);cin.tie(0);int num=1;while(num--)solve();return 0;
}