DP题解

题目大意
求从（1,1）到（R,C）所需的最短步数。

思路
广搜。
哦我不会广搜
还有什么解法呢……动态规划！从这个点四周所需步数最少的点走过来就能得到这个点的最优解。
设当前状态dp[i][j]为走到该格所需的最小步数，则状态转移方程为

dp[i][j]=min(dp[i][j],min(dp[i-1][j],min(dp[i+1][j],min(dp[i][j-1],dp[i][j+1])))+1;

于是喜提90。
花了一个探照灯得知，有些时候某个点的实际最优可能是由

dp[i][j+1]

,也就是右边来的，而此时右边还没有访问，于是只能……再从右往左遍历一遍了。
（也许还有更好的方法，但实在想不出来了）

代码：
记得将每个点初始化为极大值，还有别忘了障碍物！
谁会傻到把它忘了

#include<bits/stdc++.h>
using namespace std;
int n,m,dp[45][45];
char a[45][45];
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++)
            cin>>a[i][j];
    }
    for (int i=0;i<=n+1;i++)
        for (int j=0;j<=m+1;j++)
            dp[i][j]=1000005;
    dp[1][1]=1;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++)
            if (a[i][j]=='.' && !(i==1 && j==1)){
                dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
                dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
                dp[i][j]=min(dp[i][j],dp[i+1][j]+1);
                dp[i][j]=min(dp[i][j],dp[i][j+1]+1);
            }
        for (int j=m;j>=1;j--)
            if (a[i][j]=='.' && !(i==1 && j==1)){
                dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
                dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
                dp[i][j]=min(dp[i][j],dp[i+1][j]+1);
                dp[i][j]=min(dp[i][j],dp[i][j+1]+1);
            }
    }
    cout<<dp[n][m];
    return 0;
}

模仿洛谷的题解风格写的，求赞