| 9 | bool e(int i,int j) { return (i >= 0 && i < 7 && j < 7 && j >=0 && !vis[i][j]); } |
| 10 | |
| 11 | void dfs(int i,int j,int idx) { |
| 12 | if (i == 6 && j == 0) { |
| 13 | if (idx == 48) cnt++; |
| 14 | return; // optimisation 2 |
| 15 | } |
| 16 | if (vis[i][j] == true) return; |
| 17 | vis[i][j] = true; |
| 18 | if (s[idx] == '?' || s[idx] == 'L') { |
| 19 | if (j && !vis[i][j-1]) { |
| 20 | if ((e(i,j-2)==false && e(i+1,j-1) && e(i-1,j-1)) == false){ |
| 21 | dfs(i,j-1,idx+1); |
| 22 | } |
| 23 | } |
| 24 | } |
| 25 | if (s[idx] == '?' || s[idx] == 'R') { |
| 26 | if (j < 6 && !vis[i][j+1]) { |
| 27 | if ((e(i,j+2) == false && e(i+1,j+1) && e(i-1,j+1)) == false) { |
| 28 | dfs(i,j+1,idx+1); |
| 29 | } |
| 30 | } |
| 31 | } |
| 32 | if (s[idx] == '?' || s[idx] == 'U'){ |
| 33 | if (i && !vis[i-1][j]) { |
| 34 | if ((e(i-2,j) == false && e(i-1,j+1) && e(i-1,j-1)) == false) { |
| 35 | dfs(i-1,j,idx+1); |
| 36 | } |
| 37 | } |
| 38 | } |
| 39 | if (s[idx] == '?' || s[idx] == 'D') { |
| 40 | if (i < 6 && !vis[i+1][j]) { |
| 41 | if ((e(i+2,j) == false && e(i+1,j+1) && e(i+1,j-1)) == false) { |
| 42 | dfs(i+1,j,idx+1); |
| 43 | } |
| 44 | } |
| 45 | } |
| 46 | |
| 47 | vis[i][j] = false; // backtrack |
| 48 | } |
| 49 | |
| 50 | int main(){ |
| 51 | ios_base::sync_with_stdio(false),cin.tie(nullptr); |