小明的迷宫

#include<algorithm>
using namespace std;
int dp[1005][1005];
int main(void)
{
	int n,m;
	scanf("%d %d",&n,&m);
	char map[n+5][m+5];
	for(int i=0;i<n;i++)//字符串读入可以i从1开始，但j不可能
		scanf("%s",map[i]);
	//有墙壁的就是2的dp
	//这里数值题目感觉是刻意设计过的，让你可以提前初始化第一行和第一列
	//而不会产生绕路更少的可能，然后后面遍历的都是从前往后处理过的路径不用再区分
	//到自身为墙壁的时候再+1
	//如果数值不是这样子的话，可能dp写不了要dfs或者bfs了
	//比如你要考虑绕路直接dp四个方向，后面和下面是没走过的肯定是0，取min就直接取0了
	for(int i=1;i<n;i++)
	{//这个数值决定了哪怕有墙，第一列绕路也不可能
		dp[i][0]=dp[i-1][0]+1;
		if(map[i][0]=='1')//是要到我这里，所以dp值看我自己位置是不是墙来加
			dp[i][0]++;
	}
	for(int j=1;j<m;j++)
	{//提前处理的好处就是后续dp不用判断边界减少if
		dp[0][j]=dp[0][j-1]+1;
		if(map[0][j]=='1')
			dp[0][j]++;
	}
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<m;j++)
		{//从上到下从左到右，经过的都是处理过的dp，所以比较的时候不用担心墙壁
			dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
			if(map[i][j]=='1')
				dp[i][j]++;//但经过自身的时候墙壁要处理一下，就像前面给走过的路处理一样
		}
	}
	printf("%d",dp[n-1][m-1]);
	return 0;
}