uva 10401 Injured Queen Problem（DP）

uva 10401 Injured Queen Problem（DP）

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;
}