链接：https://ac.nowcoder.com/acm/contest/6116/C

迷宫

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

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

如果当前格子右边没有障碍物，牛妹就向右走，否则转到2。
如果当前格子下方没有障碍物，牛妹就向下走，否则转到3。
如果当前格子左边没有障碍物，牛妹就向左走，否则转到4。
如果当前格子上方没有障碍物，牛妹就向上走，否则转到5。
牛妹站在原地不动。
由于牛妹按这样的策略可能会无法走到出口，牛妹的好朋友牛牛决定在牛妹离开格子{(1,1)}(1,1)前把迷宫中的一些非障碍格子变成障碍，帮助牛妹走出迷宫，但是牛牛比较懒，他想要最小化变成障碍的非障碍格子的数量。
输入描述:
第一行两个整数n,m表示迷宫的大小
接下来n行每行一个长度为m的01串表示迷宫的格局

输出描述:

输出一个整数表示牛牛最少需要转换成障碍格子的非障碍格子的数量，如果无法帮助牛妹走出迷宫，输出−1。
示例1
输入
4 4
0000
0110
0110
0000
输出
0
备注:
{1<=n,m<=1000}1<=n,m<=1000

思路：

不难看出，如果1，2不能执行，3可以执行，那么以后将会一直左右移动，同理1,2,3不能执行，4可以执行那么以后将会一直上下移动。所以要想走出去我们就是要一直执行1或2.在这里我们可以用dp来求出所需要的添加的最少障碍数。

#include<iostream>
#include<string.h>
#include<cstring> 
using namespace std;
char s[1005][1005];
int dp[1005][1005];
int main(){
    int n,m;
    cin>>n>>m;
    memset(dp,0x3f,sizeof(dp));//初始化dp数组
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
        }
    }
    dp[1][1]=0;//起点初始化为0
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if((i==1&&j==1)||s[i][j]==1){
                continue;
            }//如果是起点或障碍物则跳过
            dp[i][j]=min(dp[i-1][j]+(s[i-1][j+1]=='0'?1:0),dp[i][j-1]);//状态转移方程求到当前位置所需要添加的最少障碍物数量
        }
    }
    if(dp[n][m]<1e9){
        cout<<dp[n][m];
    }
    else{
        cout<<-1;
    }
    return 0;
}

迷宫

迷宫

题目描述

输入描述:

输出描述:

思路：