uva 10401 Injured Queen Problem

题目大意：这是一个变形的N皇后问题，皇后不再是占据一行一列以及斜线，她占据的只是她周围的一圈以及她所在的一列。题目给出一个含有问号，数字和字母的字符串。第i个字符是问号代表皇后在第i列的任意一行，若第i个字符是数字或字母X（1～F）代表皇后在第i列的X行。求满足该字符串的摆放方式的方法一共有几种。

解题思路：从第一列开始往后递推。dp[i][j]表示的是结合j - 1列的摆放方式，将皇后放在（i, j）的位置会有几种情况。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #define N 30 using namespace std; typedef long long ll; char s[N]; int vis[N]; ll dp[N][N]; ll ans; int main() { while (scanf("%s", s + 1) != EOF) { ans = 0; memset(vis, 0, sizeof(vis)); memset(dp, 0, sizeof(dp)); int len = strlen(s + 1); for (int i = 1; i <= len; i++) { if (s[i] >= '1' && s[i] <= '9') { vis[i] = s[i] - '0'; } else if (s[i] >= 'A' && s[i] <= 'F') { vis[i] = s[i] - 'A' + 10; } } if (vis[1]) { dp[vis[1]][1] = 1; } else { for (int i = 1; i <= len; i++) { dp[i][1] = 1; } } for (int i = 2; i <= len; i++) { if (vis[i]) { for (int k = 1; k <= len; k++) { if (abs(vis[i] - k) > 1) { dp[vis[i]][i] += dp[k][i - 1]; } } } else { for (int j = 1; j <= len; j++) { for (int k = 1; k <= len; k++) { if (abs(j - k) > 1) { dp[j][i] += dp[k][i - 1]; } } } } } for (int i = 1; i <= len; i++) { ans += dp[i][len]; } printf("%lld\n", ans); } return 0; }