迷宫

链接：https://ac.nowcoder.com/acm/contest/6116/C
来源：牛客网

题目描述
有一个{n*m}n∗m迷宫，迷宫中每个格子用{0}0或{1}1表示，{0}0表示该格子可以通过，{1}1表示该格子是个障碍物，牛妹站在格子{(1,1)}(1,1)，出口在格子{(n,m)}(n,m)，牛妹想要走出迷宫，但牛妹只会按以下策略走：

牛妹当前所在的格子称为当前格子

1. 如果当前格子右边没有障碍物，牛妹就向右走，否则转到2。

2. 如果当前格子下方没有障碍物，牛妹就向下走，否则转到3。

3. 如果当前格子左边没有障碍物，牛妹就向左走，否则转到4。

4. 如果当前格子上方没有障碍物，牛妹就向上走，否则转到5。

5. 牛妹站在原地不动。

由于牛妹按这样的策略可能会无法走到出口，牛妹的好朋友牛牛决定在牛妹离开格子{(1,1)}(1,1)前把迷宫中的一些非障碍格子变成障碍，帮助牛妹走出迷宫，但是牛牛比较懒，他想要最小化变成障碍的非障碍格子的数量。

输入描述:
第一行两个整数{n}n,{m}m表示迷宫的大小
接下来{n}n行每行一个长度为{m}m的{01}01串表示迷宫的格局
输出描述:
输出一个整数表示牛牛最少需要转换成障碍格子的非障碍格子的数量，如果无法帮助牛妹走出迷宫，输出{-1}−1。
示例1
输入

4 4
0000
0110
0110
0000
输出

0
备注:
{1<=n,m<=1000}1<=n,m<=1000

题解：这个题目看起来像是深搜，但是数据过大，所以不是深搜，实际上是dp算法。因为只能向下或向右走（向左或向上走会死循环），就有两种方法去推这题。第一种：直接从左边过来，第二种：上面的右边有障碍，直接从上面过来，第三种：上面的右边没有障碍，需添加一个障碍后从上面过来。

dp公式：dp[i][j]=min(dp[i][j-1],dp[i-1][j]-a[i-1][j+1]+1);

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,a[1005][1005],dp[1005][1005];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    char ch;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cin>>ch;
            a[i][j]=ch-'0';
        }
    }
    for(i=0;i<=max(n,m)+1;i++)
        a[0][i]=a[i][0]=a[i][m+1]=a[n+1][i]=1;
    memset(dp,127/3,sizeof(dp));
    dp[1][1]=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(i==1&&j==1)
                continue;
            if(a[i][j]==0)
                dp[i][j]=min(dp[i][j-1],dp[i-1][j]-a[i-1][j+1]+1);//如果没有障碍会加一。
        }
    }
    if(dp[n][m]>1000000)
        cout<<-1;
    else
        cout<<dp[n][m];
    return 0;
}