fork download
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. int32_t main() {
  6. int T;
  7. cin >> T;
  8. int cases = 1;
  9. while(T--){
  10. int n;
  11. cin >> n;
  12. vector<vector<char>> vec(n,vector<char>(n));
  13. vector<vector<int>> dp(n,vector<int>(n));
  14. vector<vector<bool>> visited(n,vector<bool>(n));
  15. int startY = 0, startX = 0;
  16. for(int i = 0; i < n; i++){
  17. for(int j = 0; j < n; j++){
  18. cin >> vec[i][j];
  19. if(vec[i][j] == 'W'){
  20. dp[i][j] = 1;
  21. startY = i;
  22. startX = j;
  23. }
  24. }
  25. }
  26. for(int i = n-1; i >= 0; i--){
  27. for(int j = 0; j < n; j++){
  28. if(visited[i][j] == true) continue;
  29. if(vec[i][j] == 'B'){
  30. if(i + 1 >= n || j + 1 >= n) continue;
  31. if(dp[i+1][j+1] >= 1){
  32. if(i - 1 < 0 || j - 1 < 0) continue;
  33. if(vec[i-1][j-1] == 'B') continue;
  34. dp[i-1][j-1] = dp[i+1][j+1];
  35. visited[i-1][j-1] = true;
  36. }
  37. if(i + 1 >= n || j - 1 >= n) continue;
  38. if(dp[i+1][j-1] >= 1){
  39. if(i - 1 < 0 || j + 1 >= n) continue;
  40. if(vec[i-1][j+1] == 'B') continue;
  41. dp[i-1][j+1] = dp[i+1][j-1];
  42. visited[i-1][j+1] = true;
  43. }
  44. }else{
  45. if(j-1 >= 0 && i + 1 < n){
  46. dp[i][j] += dp[i+1][j-1];
  47. }
  48. if(j+1 < n && i + 1 < n){
  49. dp[i][j] += dp[i+1][j+1];
  50. }
  51. }
  52. }
  53. }
  54. int ans = 0;
  55. for(int i = 0; i < n; i++){
  56. ans += dp[0][i];
  57. }
  58. printf("Case %d: %d\n",cases, ans);
  59. cases++;
  60. }
  61. }
  62.  
Success #stdin #stdout 0s 4280KB
stdin
100
2
B.
W.
13
.B...B......B
....B......B.
............B
....B....B...
.W...........
......B.B.B..
....B....BB..
.BB..B..BB...
.....B...B..B
.B....B......
B.B.B....B...
...B...B.....
.....B....B..
17
.........B.......
.B..B............
....B............
.B...........B...
.B........B......
.................
.W...B...........
B........B.......
.............B...
............B...B
......B..........
..B.....B........
...B.............
.....B.........B.
..B.........BB.B.
...B...........B.
...B.BB....B....B
25
................B........
....................B....
.........B...........B...
.........................
..B......................
.........BB.B.....B......
.B.......B........B......
.........B......B.....B..
.BB....B.....B...B.......
.B.......................
.....B...................
.........................
......B...B..B........B..
B............B...........
......B..................
.....B..........B........
..B...........B..........
..B...B..................
.........................
...B................B....
..................B......
.........B..BB.....B.W...
...............B.........
....B.................B..
.....BB..B...............
20
.B.....B.B....B....B
....................
.B..B...............
....B..B..B......B..
......B..........B..
.B..................
BB....BB.B.B......BB
BB........B......BB.
.................B..
..............B.....
..B...B..B........B.
.....B..............
..B.........B...B...
....................
.B.B..B.....B.......
BB.B..........BB....
.WB....BB.....B.....
....................
.B..B...B....B......
...BB..B.....B......
5
.....
.....
W....
.....
.....
2
BB
.W
11
...B..B...B
.B.....B...
...B.BBB...
.B..B.B.BBB
.B.B...B..B
..B..W..B.B
.BBB.BB.B..
B.B..BB..BB
B.BB..BBB..
.B.B.......
.......B...
21
.B...................
...........B.........
..B...B..............
...B.................
...............B.....
................B....
.......B.............
B....................
..............B......
.....................
............B........
.....................
B...................B
...................W.
............B.B......
.....................
.B...................
.....................
.....................
.......B....B........
.....................
12
............
B.B.B.B....B
............
B..W...B.BB.
BB.......B.B
.B.......B..
..B...BB..B.
..BB.....B..
...B...B..B.
....BB...BB.
B.BBB.......
.BB.BB.....B
2
.B
.W
8
........
.....B..
...BB.B.
.....B..
........
......B.
..B.....
...B..WB
10
..B.......
.....B....
..........
.....B....
B.B.......
..........
..W.......
.B........
..B....B.B
.........B
14
B...B.......B.
BB......B.....
.......B.....B
...B..B.....B.
....BB..B..WB.
.........B....
.............B
B.B..B........
.BB........B..
.BB......B..BB
B........B...B
B.B.B.......B.
.....BB...B...
B.B..B...BB...
2
..
W.
12
..B........B
BB....B.BB..
B.B..BB.B...
B..........B
.BBB....B...
............
.......B..B.
.BB.B..B....
B......BW..B
........BB..
..B.BB......
..........B.
3
...
W..
...
19
...................
...................
.B.................
....B..............
...................
...................
...................
...................
...................
...B...............
...................
...................
.........B...B.....
..W.......B........
...................
...................
...................
..........B........
.....B.............
17
.................
...........B.....
...........B.....
.................
...B.............
....B............
.............B...
.....BB..........
........B..B.....
.......BBB...B.W.
...B...........B.
.B...............
.......B.........
........B........
B........B......B
....B............
.................
17
.BB.......BB...B.
.BB.B...BBB.....B
...B..B....B.BB..
.BBBB.BBBBBB....B
BB.BB....B..B....
...BBB.....BBB.B.
BB..BB...B...B...
.B.....BB.....B.B
BB.B..BBB........
..BW....B......BB
BB.BBB.B.B..B....
BBB....B...B.BB..
BB..B...B.B..B...
B.BBB...BBB....BB
.....BB.....B...B
..B.....B..BBBB..
B..B....B.B...BB.
7
.......
B......
.B.B..B
..BB..W
.B.....
.......
...B...
28
....B.B.B........B....B.....
BB....B............B.B..B...
B.B.....B........B..B....B..
.B.....B...........B........
..........B.......B..B......
..........BB........B....B..
...............B..B........B
..B.W.....B.....B.B.........
..B..B...B.......B.......B..
...B......BB.B..............
........................B..B
B......B..B........BBB....B.
......B.B...B......B...BB...
..............B........BB...
...B.........B...B..........
........B............B...B..
B.B......B..........B.......
B.....B.B.....B.............
.......B...B.......BB.......
....BB.........B...B.BB.....
.....B....B....B.BBBB.B....B
.......B..B....B.....B....B.
..B.........B.....B........B
..B.............B......B....
.....B....B....B...B.....BB.
..B...B.B.......B..B.B.....B
B....................B.....B
.B....B.B................B..
15
....BB..B.....B
...B...........
.....B.......BB
..B.B.B...B.B.B
............BBB
.....B..B.....B
.BBB....B...BBB
BB...B....B.B.B
...B..B......B.
.B..BB...B..B..
B..B.....B.....
WB...B....BB...
B.BB....B.BB...
.B.............
....B.B...B....
18
.B.....B..........
..B...............
.........B........
..B..B............
..................
.B.B..............
B...B....B........
..................
..........BB......
.........B.B..BB..
......BB.BB....BB.
..B....BW.B.B.....
.BB.......B.......
...B.....B........
..B......B.......B
........B.....B...
....B.............
................B.
20
....................
....................
....................
...................B
....................
................W...
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
......B.............
....................
30
............B.............B...
...B.......B.......B..B......B
..BB..........................
.............B...........B.BB.
.....B..B.B...................
..B.......B....B.....B....B...
............B...B.....B.B.....
........B.B.............B..B..
.............B...........B....
..B...............B.B.B.......
.....B........B...............
...B.........B.........B.B..B.
.........B.B..BB...B......B...
.B............B...............
.B...B...............B........
BB.............B......B.B.....
...BB....W......B...........B.
.........................B....
.........................B....
.................B............
............B.......BB......B.
....B..........B....B.........
....BB............B..B........
........B.B...................
.........B...........B.BB.....
............B....B........B...
..B......B.....B.B.....B.....B
...B...........B....BB........
..........B..B....B...........
B...................BBB..B....
15
B...B........B.
BB..........B..
..B............
.........B.....
...B...........
........B......
.....B.B....BB.
..B.........B..
...............
......BB.BB....
....B..........
..........BB...
.BB....B.......
.......B......W
....B..........
8
..B.....
........
........
..B..B..
........
..W.....
B.......
........
26
............B..B......B...
.............BB....B...B.B
....BB................B...
.....B...B......BB........
B....W....B...............
.....B....B..BB...........
B.........................
..................B..B....
.B...B.....B.....B..B.....
..........................
..B.................BB....
..........B.B...B.........
................BB.B....BB
...........B..............
...............B......B...
....B.....B.B.............
...................B......
.....B.....B........B.....
......BB.B..B.B.........B.
.B...B...............B....
.B...B.B........B...B.....
..B..B...BBB.......B...B..
.....B..........BB........
.BB......B....B.B........B
..........................
.B..B.....B...............
20
....................
W...B...............
....................
...................B
..........B.........
B...................
....................
........B........B..
....B...............
................B...
..................BB
....................
.........B..........
....................
..........B.........
....................
.B.B...........B....
B...................
...B..............B.
....................
3
...
W..
...
10
..B.BB.B.B
......B...
.BB....B..
BB.BB...B.
.B..BB.B..
BB...B....
....B.B.B.
BB....B..B
.BB...B.B.
.W...BBB..
21
.........B..B........
..B.......B.........B
B.....B...BB........B
...B........B...B....
BB....B.B.BB...B..B..
...B..B..............
.B..B.B.B...B........
.B...B......B....B..B
............B.B......
...........B...B.B..B
...B.BBB...B.B....B..
...........B.BB......
..B.B..B...........B.
.............B.....B.
WB...B.....B.....B...
...B.B.....BBBB.....B
...B...B.........B..B
............B.......B
...B...B..B..B.B.....
................B....
B.B..B..........B....
10
B....BBB..
BB.B.B....
B..B......
.B..BB...W
BBB.......
.B....BB.B
.BBB..B.BB
......B..B
B...B...B.
.....B....
15
..B..B.........
.B.........B...
.........B.....
B.B.....B......
.B...........B.
..B............
B..............
.B..B.....BB..B
...........B...
...B...B.B.B...
.B..B........B.
B..B...........
............B..
.....B..B...BB.
...B.B..W......
31
BBB...B..B..B.B....BB..........
BB....BB.BBB.....B.BBB.BBB.B...
B....B...BBBB.......BB....BB.B.
.BB..BB..BB.BBBB.B....B..B..BBB
..BB..B....B.B...B..BB.BBBB.B..
.B.B.B..BBB.....BB............B
.B.B..B.B...BB.BBB..B.B....B.B.
B...B........BB.BBB.B..........
.B.....B.B...B.....B..B.B..BB.B
..B...B...B.BBBB.BB..B.....BBB.
...B..BBB.B..B.BB....BB....B..B
..BB...B....B.BBBB...B.BBB.B...
B.B.BBB.....B.B.B.BB.BBB.BBB..B
B..B....BB.B..B...BBB.BBBBB..B.
BB...B.....B.B.BB.B.BB.BB.BB...
..B...B....B.B.B.BBBB.......B..
B...BBB....B...W...B......B....
B..B.B.BBB....BB.BB.B.B..BB.B..
B.BB..BBB.BBB..B.B..BB..B....BB
..B.BBB..B.B.B.B.BBB.BB.BB....B
...BB............B.B..B...B....
B.BB..BB...BB.BBB.B....B.......
..BB..B.B.BB..B....B.....B..B..
..BB.B.B.B...........BB..B..BBB
.B..BB.BBB..B..........B..B..BB
........B.B..........BB.B....B.
B.B.B...B.....B..BBB....B..BBBB
BBB....BBBBBB.B....B.B..B.B....
.BBBB...BB.B...B....B.B...B...B
.....B.....BB.....B..BB.B..B.B.
....BB.B..B.B.....BB.....BB...B
21
.B....B.BB..B..B..BBB
...B.B..BB...B..B.B..
W...B.....B.......B.B
BB..B.....BB..B......
...B...BB.B....B.BBB.
.B..............B....
..B....B............B
BB....BB...B......B..
B.......B.B.........B
B...BBB......BB...B..
BBB..B...B...BB.B..B.
....B.B.B.B.B..B.....
...BB...B..B...BB....
..B.B..BBBB......BB..
B.BB...BB...BBBBBB...
B...BB..B...B...B....
B....BB..BB.B.....B..
..B.B.B.....B.B.B...B
.BB...BBB....BB..B..B
........B.B.BB..B....
BBB..B....B..B...BB..
6
......
.....B
B....W
......
......
......
11
B.B....B...
........B.B
B..B.....B.
B.B....BB..
...B.B.BB.B
...B...BB.B
.BB.......B
BB..B......
.B.BB..B...
.....BB..WB
BB...BBBB..
2
..
.W
10
B..BBB.B.B
.B...BB.W.
B...B..B..
.B...B...B
..BB...BB.
BB...B...B
BB.BB..BBB
.BB..BB.BB
....BB..B.
.B.B..BB..
4
....
....
....
.W..
7
..B....
B...B..
..B..B.
....B..
BB..W.B
...BBBB
.B...B.
22
.B.....B.B...B.....BB.
B.....B.B.B.B.....B...
..B...B...B.B.B.....B.
.B....B..B.B....BBB...
......B...B..BB.....B.
....B....B.......B.BBB
B.B......B........B.B.
..B..B.B...B....B....B
.B....BB..B...BB..B..B
...BB.B.B....B...B....
B...B.B..W..B.B...BB..
....B.......B.B..B...B
B..BB.B.......BB.B....
..B.BB..B..B.BB.BB....
......B.....BB...B...B
B.....BB.B........B...
......................
.......BBBB...........
............B....B....
.BB..B..BB.B..........
....B.B...B....B......
.B...B.......BB..B...B
24
.....B...BB..........BB.
B.B.BB...B.BB..B.BB...BB
B...BB.B.B....B.....B..B
BB..BB.....B.BB.B...B...
......B.BB...B.....BBBB.
.....BB.B...B........B.B
..BB........B....B......
B.B..BB..B....B.....B.B.
..B.BB.....BB...BB.....B
..B.BBBB....BB..B...BBBB
..BBB....B..B....B..BB.B
.B.B.BB..BBB..BB....B..B
B..B.....B..BBBB.B......
...........BB..BB...B...
.B.........WB..B..B.....
.B...B.....B........B..B
..B..BB.BBB.BB.BB.BBBB..
BB..BBB...B.B..B.....B..
...B.....BBBB.B.BB..B.BB
....B.B.B....B.B.B..B...
...B.BB..B.B.B......B.BB
....BB.B....B.BBB..B....
B....B..B..B...B......B.
BB...BB..B.B...B..B..BBB
10
..B.....B.
..B......B
..........
.B..BBBB.B
.B.BB.....
..B...BB..
.B.B..B...
BBB.B.B...
BB...W....
.......B.B
28
............................
...B........................
.................B..B.......
........W...................
..............B.............
..B.........................
..............B.............
............................
...BB..................B....
..B.......B............BB...
B....B.........B............
...B........................
............................
B.............B.............
...B...........B......B.....
............................
.B..........................
.....................B......
B........................B..
............................
.......B..B.................
....................B.......
............................
.........B.B................
.............B..............
......................B.B...
............................
............................
22
.B....B.B.B...........
..B..B....BWBB......B.
BB.BB...B.B.BB.BB..BBB
BB...BBBB...B.........
.B.BBBB.B.B.....B.B..B
...BBB........B..BBB..
...B......B.......B.BB
...B.B....B..B.....B.B
B...B.B..B...B.BB..BBB
....BBB...B...BBB..B..
...BBBB......B.BB....B
.B....B..BB....B..BBBB
..BBB.BBB..BB.B......B
B..B...BBB.B.BB...BB..
..B.........B..BB.B...
..B.....BBB...B.B.B.B.
.B..B...BBBB......B...
B.....BBB...B..BB.B...
B...BBB....B........B.
.B...BBB..B...........
BB.BB..B..BBB.....BB.B
...BB.B.....BB.BBB....
31
...B.........................B.
.......B.B........B.BB.........
..B......B.....................
......B..............B....B.B..
B..........................B...
..............................B
......B.B.......B...B..........
..B.....B.................B....
...................B...........
.B..............BB.............
...............................
B......B.......................
.B.............................
B...........................B..
......................B...B....
.....................B.........
...............................
.......................B..B....
.........B.................B...
......................B........
B......B.........B......B......
...........B.....B......B....B.
....B....B....................B
..............B..B.......B.....
.B.............................
B..B.........B............B....
................B........BB....
..B.............B...........B..
....BB....BB.......B..........B
.W...B.B........B..........B...
.....................B.B.......
28
.........B.B.....B........B.
B..B.......B..BB.....B......
.B......BB.BB...B....B..B...
B.B.......B...B....B..B....B
B.....B..B.....B.B..B......B
...BB..B....B......BB....B..
.BBBB...B..BB...B.......B...
..BB..B.BBB......BB.BB......
...BBBB....BBBB..B..........
..B..B...B.B.BB.....BBB.B.W.
........BBBBBBBBB.BB..BB...B
...BB.B.B.BB...B.B..B..B....
....B.B..BBB.B..B.B...B...BB
B...B.BBBBB.BB....B.B....BBB
.B.B..BBBB.BBB.......BB...BB
.......B.BB...B...BBB.BB...B
BB.B..B..B........BBBBBB....
.B..BB.B..B...BB...B...B...B
....BB....B.B.B....BB.B..BB.
.B.......B..B...B.BBB....B..
.B...B..B..B.B............B.
.........BB.BB.B.BB..B..B...
.BBB..BB..BB..BBB.......B...
...B...BB..B...BB....B..BB..
.B.....BB.....B...B..B...B..
.....B...B..B..BB..B.BB..B..
B.B..B.B.BB.B..BB....BB.....
B.BBBB.BBBBB....B....BB.....
19
...................
...W...............
...................
......BBB.....B....
.......B.....B.B...
........B....B.....
.B.......B....B....
...B.......B.......
.....B.............
.......B...........
........BB.........
..B..........B.....
.............B.....
..B....B......B....
....B..B.......B...
B...B..............
...................
........B..........
B..................
24
BBB......B.......B...B..
....BBB....B.......B..B.
....BB.BBB..B......B....
...BB.B......B.......B..
.B..............B...B..B
B.B.......B...B.......B.
.BB......B..............
..B........BBB..B...B...
...B........B.......BBB.
B..B.....B....BB..B....B
...B.........B...B..B...
.....B...B..........B...
...B......B....B.....BW.
..............BB.......B
........BBB..B.BB..BBB..
.B.....B................
............B.......B.BB
..B.B..BBB...B.B........
.............B.........B
........B.....B.BB.B.BB.
....B.B......B....BB..BB
...B...B...B.........B..
.....B.B..........B....B
.B...B........B...B...BB
17
B..BBBB.B.BB..BB.
....B.B...WBB....
B........B..B...B
BB.B..B.........B
..........B......
..B..B.B.B......B
......B.....B.BB.
.B.....BBB..B....
B...BB..........B
B..B..BB.B....B.B
B.BBBBB......B..B
.....BBB..B.....B
.........B..B....
..B.......BB..BB.
...B..B........B.
...B.......B.B..B
.B.....B..BB..B..
16
B....B...BB.....
.BB..B...BBB....
B..B.B.......B..
B......BB.B...B.
..B........B.B..
.....BB.B.BB....
..........B.BB..
....B....B.....B
B.....B.....B...
B..B........B..B
.BB.B..B........
...B..BBB.BB.B..
..........BB.B.B
.B.......B.BB..B
.............BW.
..BB...B......B.
18
..................
..................
..................
..................
..................
..................
..................
..................
.W................
.........B........
..................
.....B..B.........
..................
.......B........B.
..................
..................
..............B...
..................
29
.........B...................
....B........................
.............................
.............................
...................B.........
............B................
......B............B.........
.............................
..........B..................
........................B.B..
.............................
.............................
.............................
.............................
.........................B...
.............................
.....................B.......
................W............
....................B....B...
..................BB......B..
...................B.........
.............................
.B...B.......................
...............B.............
...................B.........
.............................
.............................
........B.B..................
...............BB............
18
.B.........BBB.B..
..B.B...W.........
.......B..........
...B.B.B.B.....B..
B.................
.............B..B.
B..B....B.........
........B.B..B....
...B.BB...........
.B...........B....
.......B......B...
...............BB.
..........B..B.B..
.B......B....B....
.B.......B.....BB.
...B......B.......
......B...........
......B.B.B.......
21
....B..BB.B.B....B..B
.B........BBB..B.....
B...B...B..B....BBB..
......B........B.....
B..B..BB..B...B.B....
.......W.B...........
..B.....B.B.B........
.BB.............B....
BB.B.B.....B..B.B..B.
....B..B...B.....B..B
B.B......BB.B.BB.B...
.BBB....BB.......BB..
.....B.BB..........BB
....B.B....BB.B......
B.B..........B..BB..B
..B........B..BB..B..
..B.......B..B.....BB
B.....B..BB.B.....B.B
..BB...B......B.B....
.....B.....BB.B.B.B.B
BB...........B.....B.
13
B..B.B.......
.B..BBB...B..
......B....B.
B.B..B.......
BB....BBB...B
B..BB.BBB....
BB....B......
BBBB.BBB...B.
....B.B...W..
B.B.B.B......
BBB...B..BB..
B...B...B....
B.......B.B..
15
.......BB......
........W.B....
..B.B...B...B..
..B.B..........
.....B.......B.
.........B.....
...........BBB.
...............
..........B.B..
....B......B...
...............
BB....B........
.B.B...BB......
.........B..B..
.........B.....
8
.B.BB...
...B....
........
.....B.B
B..W....
..BB..BB
........
.BB.B.BB
27
.B.BB.BB..B....B.B.B.B...BB
..BB...B.B.B.B.B.BB.B.B.BB.
..B.B..B...B.B.BBB..BB.B...
.B..BBBB....B..B.B.B.B..BB.
BB.BB...B.B....B.B........B
......B...BB.....B.B.BB..BB
...B......BBBBBBB.....B..B.
..B........W.B..BB..B...BBB
BB..B.....BBBB.B.......BB.B
....B.B..........BB.......B
.BB....B.B.B...B.B......B.B
...B.....B.B...BB.BB.B...B.
..B.BB.B.B.B.BB....BB..B.B.
....B..BB..BBBBB.B.BB..B.BB
.BB....B.B.......B......B..
...B..B.BBBB.B.B.BBBBBB....
.BBB.......BB.BBB.BBB......
.BB.B.........B..B.B.B.B..B
BB.B.B.B..B..B......BBB....
..B..B.BB...BB...B...B..B..
B..B..BBBB..B.B..B.B....B..
BBB.B.BB.B..B..BB...B......
.B..B.BBB...............B..
.B...B..BBBB......B........
BB.BB...BB.BB..B.BB.B..BB..
BB..BBB...B....BB..BB....B.
.B..B.BB..BBB..B....B...B.B
17
.......B..B......
.................
B..........B....B
.......BB......B.
........B........
......B..B....BB.
B....BB..B...B...
..B.....B..B.B.B.
...B..........BB.
......B......BBB.
.....B..B......B.
...........B.....
..B.....B..B.....
...B..W.........B
.B...............
.........B.......
.......B...B.....
9
.....BBB.
.B..B....
.....B...
....B..B.
......B.B
...B.B...
....B....
....BB...
....W...B
18
....B.B...........
..............BBB.
BB.B..BB...B......
...BBB.....B..B...
.........BB...B..B
....B.B...........
B.........B.......
..B...B..B........
.....B...B..B...BB
BB...B.B..........
B.......BBB..B..B.
..........B.......
B....B...WBB.....B
B.B...............
.............B...B
B......B..B.B.....
...B.B.B.........B
.BB..B..........B.
31
................B......B.......
....B....BB.............B......
B...........B.B..B.....B.......
...........B.B..B.........B....
...............B...............
.........B...............B..BB.
.........................B.....
.........B.....B.B.B.B.B......B
..B.....B.......B.............B
.............B.....B..B.......B
....BB..........B...B.....B....
B............B.................
..B..B......B.......B..........
.....B........B...........B....
...B.......B...B...............
.B.B....BBB.B....B......B.....B
.......................BB......
B..........B...................
...........B.B........B.....B..
.....................B.........
B............BB...B.........W..
..........B..B.................
...B.........B........B....B...
B.....................B........
....................B........B.
..........B....................
.....B.........B.....BB........
B.........B.......B............
..........B......B.............
........................B......
..B....B.B.....................
21
BB...B.B......B.BB...
...B..B.....BBBB.....
......B......BBB.B...
.B.....BB...B.B..B...
.BBBB.BB.......B.....
B......B.B....BWBB...
....BB...B..B...B.B.B
B.B..BB..B..B..BB.BB.
..B.B.B..B..BB..B.BB.
B.B.B.B.B.BB....BB.B.
.BBBB..B...BB..B...BB
.B.BB...B...B..B....B
.B..B.B...B.BB.BB.BB.
..B..........B..B.B..
.B.B...BBB.B.BB..BB..
B.....B.B.....B.B.B.B
.BB.B.B.B.BB...B.....
..B...BBB...B........
..BBB..B..B.......BB.
..BB...BBB.B.B.B.B...
B...B..BB..B.B.BB.B..
26
.BB.BB....BB.BB..B.......B
BB.B..BB..BBBB.......B....
B..BBB...B..........B...B.
......BB..B.BB.B.BBB.B..B.
B.BB..B..B..B...BB..BBB...
B.BB..B...BB.BB.B..B..B...
.BB.B...B.......B.B....B.B
BB..B.......BB.BB.B....B.B
..........B...B..B...B....
.....B.B..B...BBBBBBB..B..
BB....BB.B.BB..B....B.BB.B
...BB.B.B.B.BBBBB.B...B...
B.B...B...B.B.....B.B...B.
....BBB..B..BBBB.....BB..B
....BB..B..B.B..B.BB...B.B
BB.....B..BBBBBB.B.B....BB
........BBB.BB...BB.B...B.
...B..BBB...B.B..B...B.B..
B.........BBBBB.B.BBB..B..
.....BBBB.BBB.B.B....B.BB.
..........B..BB.....BB....
BB..WB...BBB...BBBB...B.B.
.BBB.B.BB..B.B.....BB.BBB.
BB...B.BBBBB..B..BB.B....B
B.B.B.BB..B..B...B...B.B..
..B.BBB..BB....B.B......BB
24
B.....B.BB..B.B..B......
..BBB....B.....BB...B.B.
B.......BB.......B......
.B......B.B..B...B....B.
..BB.....B.BB...B.B..B..
B.BB..BB..B.BB..B.BBB.B.
BB....B...B.B...BB.B....
.B...BB...........BBB..B
BB...BB..B.......B..BB.B
.......B.......B.BBB..B.
..B.B....B..BBB..B......
..B...B.B...B..B........
.B....B......BB...B.B...
..B...B...............B.
B.............BB......BB
...B.....BBBWBB...BB.BB.
....B...BB....B....B..B.
BB....B.B.BB..B....B...B
..BBB..B..B...BB...B..BB
...B.....B..B..BB.BBBB.B
......BB..B.....B.B..B.B
.BB.....B.B.BB.B.....B..
..B....B.B.B....B.B.....
...B..B.B.B....BBB......
22
..........B...........
.....B................
......................
......................
......................
.B....................
.B...................B
......................
............B.........
....B..........B......
......................
...B......B........B..
...............B......
...............B......
....B.................
.............B..B....B
......................
..................B...
...............B..B...
......................
................B.B..B
..........W..........B
2
.B
.W
13
BB...B.......
..B....BBB..B
....B...B....
.B.....B....B
....BB...B...
.......B..B..
....B....B...
..BB.........
...B.....B...
B............
....B........
...B..W......
.B.B..BB.....
12
.......B...B
..BBBB.B....
............
.B.B..B.....
..BB....W.B.
............
..B.......B.
.......BB...
...BB.....B.
..B.B.BB....
.B...B...B..
..B....B.BB.
29
.BB..B...B.B....BB...B....B..
.BBWB......BBBBB........BB...
...B.....B....B.B..B...BB.B.B
...B.B.....BB..B.B...BB..B...
.BB.........BB.....B.BB.....B
......B.......B....B.B.BB.B..
..BB......B.B...B.B..B...B...
..B...B.B......B..B..B...B.B.
...BBB....B..B.BB..B..BB.BBB.
.......BB.BBB.....B.B..B...B.
.....B..B...B.B.BB..B...B.B.B
B.B...B..B..B.......BB..B....
B......B.BB...B.B.........B..
..BB....B......B.......B.....
.....B......BB...BB...B....B.
B...B...B.....B.B.B..B.BB...B
.B..B........B.B....B.BBBBB..
...B...B.B.....BB.B.B.B..BB..
B....B...B...B...........B...
.B.......B.........B...B.....
.BB.....B...BB.B...B.......B.
B........B......BB........B..
.BB.B..BB.B....B....B......B.
B....BB.B.B.B..B..B....B..B..
....B.......B..B.BBB.....B...
...B.B.......BBB...B........B
.B...BBB..B....B..BB.........
BB......BB......B..B......B..
B....B...B.BB...B............
28
BB..BB..B.BBB.....BB.BB.B...
B....BBB....BB.B.BB...B..BBB
..B.B........BBBBB.B..BB..BB
..B......B..........B..BB..B
B............B....B..B..B...
B....B...B......BBB..B....BB
.BB..B.B.B........BB..B.B.B.
.B.BB..BW..B.BB........BB..B
B.BB...B..B.BB..B....B......
...........B.BB..BB......B..
B..B......B...B...BB.....BB.
.......B.B....B.B.B.......B.
.B.B.BBBB.........B..B.B..B.
...B..BB..............B..BB.
..BBB...B..............B.BB.
B.B...BBB.B.B..BB..BB..B...B
.BB.B..B......B..B...B......
B....B......BB..B..B...B....
B.B.B.B.BB..BB...B......B...
BB..B.B.B.........B.BBB.B.B.
.B.B......B...B..B....B.B.B.
..B.B...B.B.B..B.......BB...
B..BBB.B.BB.B.B..B..B.B...B.
.B.....BB...B....B..B.BBBB.B
....B.B...B.......B..B.BB.B.
BB.B.B.BB.BB..B.BB....B...B.
B...BB.B....BB.BB.B....B..BB
B.......B..B...B..BB.B.B..B.
19
........B.B...B..B.
B.B......B..B.B.BB.
........B.B........
......BB.....B..B.B
.B.BB.B..B..B..BBBB
BB.B..B.......B..B.
..B...B............
BB.B.B........B..BB
............B..B...
.B.B...........B.BB
.B..B......B.B...B.
.B...B..........B..
B....B........B.B..
....B.B.BB..B.W.BB.
B.....BB.BB........
..B.B.B....BB......
......BB.....B.BB..
B.....B..BBB..BB.B.
.....B..B....B....B
14
....B...B.....
..B..B........
B...B.B...BBB.
B.........W...
.BB...........
BB.........B..
..B...........
........B.....
B.B.....B....B
..B...........
........B.B.B.
..............
...........B.B
..B...........
3
...
W.B
.BB
15
....B.....B....
...........B..B
..W.....BB.....
..B.......B.B..
...............
.............B.
B............B.
.............B.
....B......B...
......B........
.........B...B.
............B.B
B...B..........
.B.............
...............
15
..B....B....B..
...BB.BB.BB....
....B..B.......
...B.......B..B
.BB..B......B.B
B.....BB....BBB
B....BBB.......
....BB..B....B.
.B.......B.B.B.
B....B..B.B....
.BB....B....B..
.B....B......BB
.B............B
.....W....BB.BB
..B.B..........
18
BB.B..BB.B...BB..B
.....B..B..BBB.B..
BB.BB.........BB..
B.B.B.B.....BBBBBB
.B..BB.B....WB....
B..B..B.BBBB.BB...
....B.B.B.B..B.B..
B.B..B.....B.B..B.
.BB..BBB.B.....B..
.BBB....B........B
.B.BB.B.BBB.BB...B
......BBBBB...BB.B
..B..B.B.BBBBBBB..
..B.B...B.B.BB.B.B
.BB...BBB.B.......
BBBBB.B..B...B..B.
....B........B.B.B
.B....B.......BB..
25
..B.BB.B....BBB.B..B.BB.B
.B....B.............B.BBB
.BB..B.B.B..B........B...
B.BB.BB.B.....B....BB....
B..B..B..B......B.....B..
.B.B..B..BB...BBBBB.B..BB
..B.........BB..B.....B.B
..B..WB...B.B.B.B..B..B.B
...BB..B.BB.B....B.BB..B.
BB.....B..B..B.B.BBBBB...
.BBB..BBB.....B...B.BB..B
.....B.....BB.B..B....B..
....B....B..B..BB..B.B.B.
B..BB..B...B.B.BBBB....B.
.B.BB...BB..B.B....BBB.BB
.BBB...B..B...BB.BB.....B
.B.B.B.B..B..B....BB..BBB
...B.B.BB.....BB....B....
.B.B..B.BBBBB.BBB.B......
B......BB..BB...B.B...B.B
.B....BB....B...B.B.BBB..
.B..B.....BB......B.B.B..
.BB......B.BB....BB.BB.BB
...BBB......B..B......BB.
BB...BB.B...B.......BB...
18
B.........B.....B.
.......B..........
..........B.......
...........B......
..................
..................
..................
.........B..B.....
...........W......
B.................
..............B...
B....B............
.B..B.............
........B.....B...
..................
..................
............B.....
...........B......
3
...
B..
BBW
26
.B..B....B.....BB..B......
...B........B.............
B..B.........B........B..B
.....B.B.........B........
..B.........B...B.B.......
.......B...BB.............
B..........B...........B..
B..B...BB....B..B.B..B..B.
..B.B.B.W.........B.......
.....B...B.......B.......B
........B..........B...B..
....B.......B......B..B...
.....................B.B..
..........................
B......BB.................
B..B......B...B..B........
.....B......B............B
.............B......BB....
........B....BB...B.B.....
...............B....B.B...
B.B.B............BB.....B.
..........B.....B.........
.B.....B.B..B..B...B......
..B....B...B...........B..
...B....B.....B...........
..B..B.B...B.B...........B
23
............B....B.....
B...B.B.B......W.......
.B.......B...B...BB....
......B...B..B..B..BB..
.................B..B..
..........B.B..........
..............B........
.B.............B.......
....B..........B.......
.....BB.............B..
......B....B...........
....................BBB
..B.B.......B........B.
..B.......B............
.....................B.
B.....B.B.B...B...B....
.......B...............
.......................
...B.......B..B........
.B..............B.B....
.............B.........
....B......B.......B...
B.....B....B...B.......
16
.B...B.B...B....
B.....B.BBB.B..B
...B...BB.B.B.B.
.B.B.B.B.BBB.B.B
...B.B.B..B.BBB.
BB.BB......B....
......BB..B..BB.
B..B.BB.B...B..B
..B...B.......B.
...BB...B...B...
....B.BB...BB...
.BBBB.B...B...B.
B..B......BB.BW.
.B..B..B......B.
..B..B.B.BBBB.BB
.B....BB.....BB.
19
BB....B.B....B.....
.B...........B...B.
B.....B..B...B...B.
.....B.B..B...BB.B.
..B.......B.BB...B.
..B.....B...BB..BB.
....BB......B..B...
....B.B.BB.......B.
B.BBB...W..B...B...
.BB..B..B..B..B...B
...BB..B.B....B....
BB.B.B.B...........
..B.B....BB.B..B..B
.BB........B..B..BB
.........B......B..
B.B...B..B.B.......
B..B.B.B..B.B.B....
......BB....B.B.B..
B....B.B...BB..BBB.
27
...B...B..B................
...........................
.....B...................B.
...........................
...................B.......
B..................B.......
........B.B....B.....B.....
B..........................
..............B............
.....BB..............B....B
....B...B..................
.....................B.....
........................B..
.................B.........
...........................
W............B.............
B..B.......................
................B.......B..
......B....................
.....B.....................
.......B...........B.......
.BB....B...................
........B.......B.B........
...........................
.B.B..B.....B..........B...
........B..................
...B......B......B....B....
30
.BB.......B.......B....B......
B...B...........B.............
B....B.....B...B....B.........
...B............B.............
..B.....B....................B
.......BBB...B.....B...B..B..B
...............BB..B...B......
................B...........B.
.......B......................
.BB...........B..B.B......B...
.B..........B......B...BB..B..
...........................BB.
..B.B...........B.............
B........BB...B......BB.......
B.......B...B..BB.BB..........
.B.....B.............B........
.....B...B.............BB.....
...............B.....B......B.
.B.............B..BBB.........
.......B....B............B....
.B..................B.........
B.BBB.B...................B.B.
.B..B..B....B....B..B.B.B.....
.B..........B...........B.B.B.
.......WBB....................
......B............B..BB.B..B.
..B.....................B...B.
.B.B.................B.B......
.B........................B...
.B.........B..B...........B...
14
..............
.B...B........
........B....B
..B..B........
.B............
..............
..............
.B..B.........
..............
W.............
B.............
..............
..............
..............
22
...B.........B.B......
.............B.....B..
......B........B......
...B...B..........B...
.B..B..B.....BB.B.....
.......B....B....B....
......B..B.....W...B..
...........BB...B.....
........B..BB..BB.....
...BB.B...............
.BB.B..............B..
...B....B............B
......B.........B...B.
...B.....B...B........
......................
...B...B.....B........
......................
......................
........B.............
BBB...B.B........B.B..
.B.......B............
.B..BB.....BB.........
23
.......................
..B...B......B.........
..B.........W..........
.B........B............
..B.BB.................
.......................
..............B........
.............B.........
...................B...
.................B.....
.......................
..................B....
.......................
.........B.............
....B..............B...
.......................
...........B...........
........B....B.........
.B.....B..........B....
.......................
..B....................
......B.B.............B
.......................
22
..BB..B.B..B.B.......B
BBB....BB..B.BB.B...BB
...BB.B.B.B....B...BBB
...B....B......B...B.B
B....B..B...BBB.B..W..
..............B......B
B.BBBBB.B....B..B.B.B.
..B.......BBB.B..B....
.B..B...B...B.B.B.....
..B....B.....B.B.B....
B.BB...BB.....BBB.B.B.
......B......BBBB.BB..
.B...............BBB.B
B.B....B.B....B.B....B
.B....B.B.BB....B.B...
..B..BB.B......B.B...B
..B.BB..BB............
.B......B.BB..B.B..BB.
............B.BBBB.B..
.................B..B.
B.......BB..........B.
B..BB...B...B.....B...
9
BBBB.....
.BB...BB.
..B..B.B.
.BB....B.
B...BB..B
..B...B..
BW..B..B.
BB..B.BB.
..BB..BB.
3
.B.
...
W..
16
....B....BB.B...
....B..B...B....
..BBB..B.BB..B..
...B.....BB...B.
.....B..B.......
B...B..B.....BB.
.BB..B.......B..
.........B.B.BB.
..BB...B.....B.B
.....B...W.B..B.
..BB.B....B.....
..BB...BB..BB.B.
BB..B..B...BB.BB
B.BB.B.....B.B.B
......B..B...B..
......B.........
11
BB..B....BB
B..BBB.....
.B...B.....
BBB....BB.B
BB....B.BB.
.B..BB.BBBB
B.......BB.
.B.BB.B...B
...B.....B.
.B...BBBB.W
....BB.B...
4
....
..BB
B.W.
....
28
............................
............................
............................
............................
............................
............................
............................
............................
B.................W.........
............................
.....................B......
..........B.................
............................
............................
............................
............................
............................
............................
............................
............................
............................
............................
............................
............................
............................
........................B...
.................B..........
............................
stdout
Case 1: 1
Case 2: 3
Case 3: 1450
Case 4: 605785
Case 5: 940
Case 6: 2
Case 7: 0
Case 8: 781
Case 9: 49962
Case 10: 9387
Case 11: 1
Case 12: 19
Case 13: 6
Case 14: 7489
Case 15: 1
Case 16: 239
Case 17: 1
Case 18: 1945
Case 19: 152854
Case 20: 438
Case 21: 68
Case 22: 9981738
Case 23: 25
Case 24: 283
Case 25: 30
Case 26: 4236
Case 27: 434
Case 28: 1078
Case 29: 2708
Case 30: 1738
Case 31: 1
Case 32: 490
Case 33: 42
Case 34: 390
Case 35: 4223
Case 36: 9801
Case 37: 25488
Case 38: 132
Case 39: 335
Case 40: 1
Case 41: 485
Case 42: 5
Case 43: 137
Case 44: 26082
Case 45: 76103
Case 46: 15
Case 47: 1959579
Case 48: 7720
Case 49: 4777496
Case 50: 468406
Case 51: 80180
Case 52: 708
Case 53: 3046
Case 54: 4573
Case 55: 126
Case 56: 57319
Case 57: 1772
Case 58: 45314
Case 59: 2092
Case 60: 18835
Case 61: 329
Case 62: 23400
Case 63: 2749
Case 64: 18
Case 65: 23136
Case 66: 122758707
Case 67: 1600
Case 68: 17772
Case 69: 6120
Case 70: 885553
Case 71: 1
Case 72: 1027
Case 73: 8
Case 74: 399820
Case 75: 282693
Case 76: 113051
Case 77: 1038
Case 78: 1
Case 79: 59598
Case 80: 318
Case 81: 518
Case 82: 2734
Case 83: 54286
Case 84: 35
Case 85: 500400
Case 86: 50568
Case 87: 314
Case 88: 17251
Case 89: 934505
Case 90: 231012
Case 91: 3672
Case 92: 1172686
Case 93: 3
Case 94: 10039
Case 95: 388
Case 96: 2
Case 97: 2927
Case 98: 7
Case 99: 96
Case 100: 17056