AOJ_2272

動的計画法で解ける。
dp[i][j] = map[i][j] + min(dp[i - 1][j], dp[i][j - 1])
上の漸化式を順番に当てはめていけば、その地点までの最小のセミの数になっている。
そして、dp[H][W]がこたえになる。

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1 << 20;
typedef pair<int, int> P;
const int MAX_HW = 50;
int map[MAX_HW + 1][MAX_HW + 1];
int H, W;

int dp[MAX_HW + 1][MAX_HW + 1];

int solve(){
	for(int i = 0; i <= H; i ++)
		for(int j = 0; j <= W; j++)
			dp[i][j] = INF;
	queue<P> que;
	dp[1][1] = 0;
	que.push(P(2, 1)); que.push(P(1, 2));
	while(!que.empty()){
		P p = que.front(); que.pop();
		int x = p.first, y = p.second;
		if(dp[y][x] < INF) continue;
		dp[y][x] = map[y][x] + min(dp[y - 1][x], dp[y][x- 1]);
		if(x + 1 <= W)
			que.push(P(x + 1, y));
		if(y + 1 <= H)
			que.push(P(x, y + 1));
	}
	return dp[H][W];
}
int main(){
	char c;
	scanf("%d %d", &H, &W);
	for(int i = 1; i <= H; i++){
		scanf("%c", &c);
		for(int j = 1; j <= W; j++){
			scanf("%c", &c);
			map[i][j] = c - '0';
		}
	}
	printf("%d\n", solve());
	return 0;
}