KUPC 2011 B: 蝉

その他のコンテスト

問題概要

W*H(W,H<50)のボードがある。各マスには数字が書かれている。(0,0)から(H-1, W-1)に最短距離で行く場合、経路上の数の合計を最小化する問題。

考えたこと

  • 典型的DP、というか最近見たことあるなあ。
  • DPの方が楽(自然)に書けるような気がしたけど、そこを敢えてメモ化で書いた。
  • あれっ？通らない。というか答えが負って明らかにおかしい。
  • しばらく悩んだ結果、再帰の引数の順序を間違えていたことに気づいた。訂正。AC。

本番で通ったコード

計算量O(W*H)。

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

const int MAX_W = 55;
const int INF = 1<<29;
int H, W;

char board[MAX_W][MAX_W+1];
bool visited[MAX_W][MAX_W];
int memo[MAX_W][MAX_W];

int rec(int y, int x){

	//メモ化処理
	if(visited[y][x]){
		return memo[y][x];
	}
	visited[y][x] = true;

	int &ret = memo[y][x];
	ret = INF;

	//基底
	if(y == 0 && x == 0){
		return ret = 0;
	}

	if( x > 0){
		ret = min(ret, rec(y, x-1) );
	}
	if( y > 0){
		ret = min(ret, rec(y-1, x) );
	}


	ret += board[y][x] - '0';
	return ret;

}

int main(){

	scanf("%d%d\n", &H, &W);
	for(int i=0; i<H; i++){
		scanf("%s\n", board[i]);
	}

	printf("%d\n", rec(H-1,W-1));

	return 0;
}

計算量を落とす

もちろん、DPで配列使いまわせば空間計算量O(W+H)に落とせる。