URAL 1119. Metro（容易dp）

URAL 1119. Metro（简单dp）

http://acm.timus.ru/problem.aspx?space=1&num=1119

题意：给一个n*m的方格，某人从（0,0）出发，要到达(n,m),给出k个点的坐标，当走到这些点时可以沿对角线到达，每方格边长为100，问他需走的最短路程。

思路：

 对于k个点，有dp[i][j] =  min( dp[i-1][j], dp[i][j-1], dp[i-1][j-1] )。

否则 dp[i][j] = min( dp[i-1][j],  dp[i][j-1] )。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;

const int INF = 0x3f3f3f3f;
bool map[1010][1010];
double dp[1010][1010];

int main()
{
	int n,m,k,u,v;
	while(~scanf("%d %d",&n,&m))
	{
		scanf("%d",&k);
		while(k--)
		{
			scanf("%d %d",&u,&v);
			map[u][v] = true;
		}

		for(int i = 1; i <= n; i++)
			dp[i][0] = i*1.0;
		for(int i = 1; i <= m; i++)
			dp[0][i] = i*1.0;

		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= m; j++)
			{
				dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1;
				if(map[i][j] == true)
					dp[i][j] = min(dp[i][j], dp[i-1][j-1]+sqrt(2));
			}
		}
		double ans = dp[n][m]*100;
		printf("%.0lf\n",ans);

	}
	return 0;
}