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; }