碁盤目の経路数

質問

某大学院の入試問題で、碁盤目状の経路において視点(0, 0)から終点(xmax, ymax)までの経路を求めるプログラムなのですが、ア～エの所がどうしてもわかりません。教えて頂けないでしょうか。

#include <stdio.h>

int xmax, ymax; /* 終点の座標 */
int search_path(int, int);

int main(void)
{
int n;

scanf("%d %d", &xmax, &ymax); /* xmaxとymaxを読む */
n = search_path(0, 0); /* (0,0)から(xmax,ymax)まで経路数を求める */

printf("%d\n", n);
return 0;
}

int search_path(int x, int y)
{
if (ア)
return 0;
if (イ)
return 1;
return search_path(ウ) + search_path(エ);
}

回答No.1

m-take0220 · ベストアンサー

＞ 碁盤目状の経路において視点(0, 0)から終点(xmax, ymax)までの経路を求めるプログラムなのですが、

この条件だけだと、ほとんどの場合無限に経路があるはずです。
おそらく、座標が増える方向にのみ進める(XY平面で右または上にのみ進める)という条件が付いているものと思います。

その場合、search_pathは

指定された座標から先に進めない場合、0を返す
指定された座標から右または上のどちらかにしか進ない場合、1を返す
上記以外の場合、(現在の座標から右に進んだ座標での経路数)+(現在の座標から上に進んだ場合の経路数)を返す

という仕様になっていると考えられます。

お礼

>>座標が増える方向にのみ進める
仰る通りです。情報不足ですみません。

原理を理解できたのでベストアンサーにさせていただきました。
ありがとうございました。

回答No.2

asuncion

ア
x == xmax && y == ymax

イ
x == xmax || y == ymax

ウ
x + 1, y

エ
x, y + 1

お礼

回答ありがとうございました。
とても参考になりました。