題目連結:
題目大意:
給定兩正整數 n 、 m (1 ≦ n 、 m ≦ 8 且 n × m ≦ 42),代表有一個 n 列 m 行的象棋棋盤。一開始,上面除了最左上角擺了一個「炮」的棋子以外,其他地方皆是放「卒」。
一個「炮」可以往上、下、左或是右跳過一枚棋子去吃另一個棋子。其中,一定要有可以跳過的棋子,而且只能跳過一個棋子(不能超過),還有跳到的位置一定要有棋子可以吃,否則不能移動。
試問,在最佳的移動方式下,「炮」最多能吃幾個「卒」?
範例輸入:
範例輸入一:
3 5
範例輸入二:
4 3
範例輸出:
範例輸出一:
7
範例輸出二:
5
解題思維:
這題也是典型的深度優先搜尋(Depth First Search,DFS)之題型。
從最左上角開始。對於現在的位置依序往上下左右四個方向跑到棋盤的邊緣,如果路徑上遇到了第二個「卒」,則吃吃看該枚棋子並遞迴下去搜尋。然後看哪個方向可以吃得最多棋子,該值就作為本層遞迴的回傳值。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。