fork download
copy 
  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
comments (?)
stdin
copy 
3
3 3
*..
..*
..*
3 5
*....
....*
*....
5 5
*..#.
...*.
..#.*
..#.*
*....
stdout
copy 
2
6
1
https://ideone.com/VvdH3P
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!