j122. 11957 - Checkers
Tags :
Accepted rate : 54人/71人 ( 76% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-23 01:33

Content

給定一個 n x n 大小的棋盤,棋盤上有一個白子與許多黑子,請你計算白子移動到最上方一列的所有可能路徑總數,只有白子可以移動,黑子永遠停留在原處,白子移動的規則如下:

  • 移動到的目標位置必須是空的。
  • 位於(x, y)的白子只能向前移動對角的一格,即移動到(x+1, y+1), 或(x-1, y+1)。
  • 若在位置(x+1, y+1), (x-1, y+1)上有棋子存在,可以跨過他移動到(x+2, y+2), 或(x-2, y+2)的位置。
Input

輸入資料的第一列有一整數 T (T <= 100)表示測試資料的組數

每組測試資料第一行有一個整數 N (1 <= N <= 100) 表示棋盤的大小

接下來的N行每行有N個字元表示棋盤的佈局

其中W表示白子,B表示黑子,. 表示空的位置

每組測試資料只會有一個白子

Output

對於每組測試資料,輸出格式:"Case T: S",其中T表示測試資料編號(由1開始),S表示白子移動到最上方一列的可能路徑總數,由於其值可能極大,請你取除以 1000007 的餘數。

Sample Input #1
2
4
....
....
....
..W.
8
.B.B.B..
........
........
..B.....
........
..B.....
.W......
........
Sample Output #1
Case 1: 5
Case 2: 1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
出處:
UVA [管理者: ig99lp33lp33 (위즈원) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
44433 goodlogic (GoodLogic) j122
基本dfs+memoization
41 2024-12-04 23:42