小明的迷宫

O(n²)时间，O(n²)空间。二维dp。

#include <stdio.h>
int min(int x,int y)
{ // 求最小值的函数 
	if(x<y)
		return x;
	else
		return y;
}
int main(void)
{
	char a[1005][1005]; // 二维字符数组，存储迷宫 
	int b[1005][1005]={0}; // 二维整形数组，用于动态规划 
	int n,m,i,j;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++) // 这不比你 scanf("%1d",&a[i][j]); 舒服多了？ 
		scanf("%s",a[i]);
	for(i=1;i<n;i++)
	{ // a[1][0]只能从a[0][0]来，走回头路是不划算的 
		b[i][0]=b[i-1][0]+1; // 体力 +1 
		if(a[i][0]='1') // 如果该点有墙壁，打破它 
			b[i][0]++; // 体力 +1 
	}
	for(j=1;j<m;j++)
	{ // a[0][1]只能从a[0][0]来，走回头路是不划算的 
		b[0][j]=b[0][j-1]+1; // 体力 +1 
		if(a[0][j]=='1') // 敲墙壁 
			b[0][j]++;
	}
	for(i=1;i<n;i++)
		for(j=1;j<m;j++)
		{ // a[i][j]可以由a[i-1][j]或者a[i][j-1]来，取最小值 
			b[i][j]=min(b[i-1][j],b[i][j-1])+1; // 并且体力 +1 
			if(a[i][j]=='1') // 敲墙壁 
				b[i][j]++;
		}
	printf("%d",b[n-1][m-1]); // 此时a[n-1][m-1]一定是最优解 
	return 0;
}