[14b1] 2次元の動的計画法1

幅W、高さHのますの領域中の(0,0)の位置にロボットがある。ロボット は現在位置(→で示されている)から図右灰色の位置にのみ動け、領域の外に 出ることはできない。ここではWとHは8と6にdefineする。

動的計画法により各ます目にロボットが最短何ステップで到達できるか を調べ、すべてのます目中の「最短で到達できるステップ数の最大値」 を出力するプログラムを作成せよ。図では最初にいる位置に0、未到達 のます目に-1を記入しているが、この方法に限るものではない。main以 外の関数を作成してもしなくてもよい。出力は「"%d\n"」の書式文字列 で出力すること。

記号列 

コード 

選択肢

ア #include <stdbool.h>
イ #include <stdio.h>
ウ #define H 6
エ #define W 8
オ int a[H][W];
カ int main(void) {
キ void move(int i, int j, int v, bool *chg) {
ク }
ケ return 0;
コ while(chg) {
サ for(j = 0; j < H; ++j) for(i = 0; i < W; ++i) {
シ if(a[j][i] >= 0 && a[j][i] <= v) { return; }
ス if(a[j][i] > max) { max = a[j][i]; }
セ if(j < 0 || j >= H || i < 0 || i >= W) { return; }
ソ int i, j, max = 0; bool chg = true;
タ chg = false;
チ *chg = true;
ツ a[0][0] = 0;
テ a[j][i] = v;
ト a[j][i] = -1;
ナ if(a[j][i] < 0) { continue; }
ニ move(i+1, j+1, a[j][i]+1, &chg); 
ヌ move(i+2, j+1, a[j][i]+1, &chg); 
ネ move(i+2, j-1, a[j][i]+1, &chg); 
ノ move(i-1, j, a[j][i]+1, &chg); 
ハ move(i-2, j-1, a[j][i]+1, &chg); 
ヒ printf("%d\n", max);

選択肢の行をドラグして上のコード領域に配置してください。 コード領域の行はドラグにより位置が変更できます。 削除したい場合は選択肢の領域に戻してください。