fork download
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. #define F first
  6. #define S second
  7. #define modulo ll (1e9 + 7)
  8. #define EPS 1e-9
  9.  
  10. typedef long long ll;
  11. typedef pair<int,int> pii;
  12.  
  13. void init(){
  14. cin.tie(0);
  15. cin.sync_with_stdio(0);
  16. }
  17.  
  18. const int N = 509, M = 1e6 + 9, OO = 0x3f3f3f3f;
  19. const ll llOO = 0x3f3f3f3f3f3f3f3f;
  20.  
  21. int n, m, knight[N];
  22.  
  23. bool emptyCell[N][N];
  24.  
  25. //first index is a dummy state
  26. int dx[] = {-1000, 2, 2, 1, 1, -1, -1, -2,-2};
  27. int dy[] = {-1000, 1,-1, 2,-2, 2, -2, 1, -1};
  28.  
  29. inline bool valid(int i, int j){
  30. return (i >= 0 && i < n && j >= 0 && j < m);
  31. }
  32.  
  33. inline bool valid2(int i, int m, int &newR, int &newC){
  34. if(i < 0 || m == 0) return 1;
  35. int r = i + dx[m];
  36. int c = knight[i] + dy[m];
  37. return !(r == newR && c == newC);
  38. }
  39.  
  40. int dp[N][3][5][5][7], vis[N][3][5][5][7], vid;
  41.  
  42. //Top-down approach
  43.  
  44. int solve(int i, int first, int second, int third, int fourth){
  45. if(i == n) return 1;
  46.  
  47. int &ret = dp[i][first][second][third][fourth];
  48. if(vis[i][first][second][third][fourth] == vid) return ret;
  49. vis[i][first][second][third][fourth] = vid;
  50.  
  51. ret = 0;
  52. for(int k = 1;k < 9;k++){
  53. int r = i + dx[k];
  54. int c = knight[i] + dy[k];
  55.  
  56. if(valid(r, c) && emptyCell[r][c] && valid2(i - 4, first, r, c) && valid2(i - 3, second, r, c) && valid2(i - 2, third, r, c) && valid2(i - 1, fourth, r, c)){
  57. ret += solve(i + 1, (second > 2 ? 0 : second), third, (fourth > 4 ? 0 : fourth), (k > 6 ? 0 : k));
  58. while(ret >= modulo) ret -= modulo;
  59. }
  60. }
  61.  
  62. return ret;
  63. }
  64.  
  65.  
  66. //Bottom-up approach
  67.  
  68. int solve(){
  69.  
  70. for(int first = 2;first >= 0;first--)
  71. for(int second = 4;second >= 0;second--)
  72. for(int third = 4;third >= 0;third--)
  73. for(int fourth = 6;fourth >= 0;fourth--)
  74. dp[n][first][second][third][fourth] = 1;
  75.  
  76.  
  77. for(int i = n - 1;i >= 0;i--){
  78. for(int k = 1;k < 9;k++){
  79. int r = i + dx[k];
  80. int c = knight[i] + dy[k];
  81. if(!(valid(r, c) && emptyCell[r][c])) continue;
  82.  
  83. for(int first = 2;first >= 0;first--){
  84. for(int second = 4;second >= 0;second--){
  85. for(int third = 4;third >= 0;third--){
  86. for(int fourth = 6;fourth >= 0;fourth--){
  87. if(valid2(i - 4, first, r, c) && valid2(i - 3, second, r, c) && valid2(i - 2, third, r, c) && valid2(i - 1, fourth, r, c)){
  88. int &ret = dp[i][first][second][third][fourth];
  89. if(vis[i][first][second][third][fourth] != vid){
  90. vis[i][first][second][third][fourth] = vid;
  91. ret = 0;
  92. }
  93. ret += dp[i + 1][(second > 2 ? 0 : second)][third][(fourth > 4 ? 0 : fourth)][(k > 6 ? 0 : k)];
  94. while(ret >= modulo) ret -= modulo;
  95. }
  96. }
  97. }
  98. }
  99. }
  100. }
  101. }
  102. return dp[0][0][0][0][0];
  103. }
  104.  
  105.  
  106.  
  107. inline void go(int tc = 0){
  108. scanf("%d%d", &n, &m);
  109.  
  110. for(int i = 0;i < n;i++){
  111. for(int j = 0;j < m;j++){
  112. emptyCell[i][j] = 1;
  113. char c;
  114. scanf(" %c", &c);
  115. if(c != '.'){
  116. emptyCell[i][j] = 0;
  117. if(c == '*') knight[i] = j;
  118. }
  119. }
  120. }
  121.  
  122. vid++;
  123.  
  124. printf("%d\n", solve());
  125. }
  126.  
  127.  
  128. int main(){
  129.  
  130. // freopen("knights.in", "r", stdin);
  131.  
  132. int t;
  133. scanf("%d", &t);
  134. while(t--)
  135. go();
  136. }
Success #stdin #stdout 0s 4372KB
stdin
3
3 3
*..
..*
..*
3 5
*....
....*
*....
5 5
*..#.
...*.
..#.*
..#.*
*....
stdout
2
6
1