s.c (1241B)
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 #include <stdint.h> 5 #include <unistd.h> 6 7 int a[9][9]; 8 char d[49]; 9 int res; 10 11 void backtrack(int x, int y, int n, int prev) 12 { 13 if (x == 7 && y == 1) { 14 if (n == 48) 15 res++; 16 return; 17 } 18 19 if (prev == 1 && a[x-1][y] && !a[x][y+1] && !a[x][y-1]) 20 return; 21 22 if (prev == 0 && a[x+1][y] && !a[x][y+1] && !a[x][y-1]) 23 return; 24 25 if (prev == 3 && a[x][y-1] && !a[x+1][y] && !a[x-1][y]) 26 return; 27 28 if (prev == 2 && a[x][y+1] && !a[x+1][y] && !a[x-1][y]) 29 return; 30 31 a[x][y] = 1; 32 33 if (x < 7 && !a[x+1][y] && (d[n] == 'D' || d[n] == '?')) 34 backtrack(x + 1, y, n + 1, 0); 35 if (x > 1 && !a[x-1][y] && (d[n] == 'U' || d[n] == '?')) 36 backtrack(x - 1, y, n + 1, 1); 37 38 if (y < 7 && !a[x][y+1] && (d[n] == 'R' || d[n] == '?')) 39 backtrack(x, y + 1, n + 1, 2); 40 if (y > 1 && !a[x][y-1] && (d[n] == 'L' || d[n] == '?')) 41 backtrack(x, y - 1, n + 1, 3); 42 43 a[x][y] = 0; 44 45 return; 46 } 47 48 int solve() 49 { 50 int i; 51 52 scanf("%s", d); 53 54 for (i = 0; i < 9; i++) 55 a[0][i] = 1; 56 for (i = 0; i < 9; i++) 57 a[i][0] = 1; 58 for (i = 0; i < 9; i++) 59 a[8][i] = 1; 60 for (i = 0; i < 9; i++) 61 a[i][8] = 1; 62 63 backtrack(1, 1, 0, 0); 64 65 printf("%d\n", res); 66 return 0; 67 } 68 69 int main() 70 { 71 int t = 1; 72 while (t--) 73 solve(); 74 }