UVA - 10401 Injured Queen Problem

本文主要是介绍UVA - 10401 Injured Queen Problem，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给出一个字符串，要求在n*n(n是字符串长度),然后如果str[i-1]=‘？’,那么在第i行就可以随便放，如果1-F的话，就在第i就要放在这个位置，注意的是皇后会攻击它的同一列和它周围的8个，求最多能放几个,仿照八皇后的思想一行一行的放，dp[i][j] 表示在坐标(i,j)能放几种，所以dp[i][j] = dp[i-1][k](k表示可以放的位置也就是abs(k-j) > 1)

#include <cstdio>
#include <cstring>
#include <cstring>
#include <ctype.h>
#include <algorithm>
using namespace std;
const int MAXN = 50;long long dp[MAXN][MAXN];
char str[MAXN];
int k;int main(){while (scanf("%s",str) != EOF){memset(dp,0,sizeof(dp));int n = strlen(str);if (str[0] == '?'){for (int i = 0; i < n; i++)dp[0][i] = 1;}else {if (isdigit(str[0])){k = str[0] - '1';dp[0][k] = 1;}else {k = str[0] - 'A' + 9;dp[0][k] = 1;}}for (int i = 1; i < n; i++){if (str[i] == '?'){for (int j = 0; j < n; j++){for (int l = 0; l < j - 1; l++)dp[i][j] += dp[i-1][l];for (int l = j + 2; l < n; l++)dp[i][j] += dp[i-1][l];}}else{int sign;if (isdigit(str[i]))sign = str[i] - '1';else sign = str[i] - 'A' + 9;for (int l = 0; l < sign - 1; l++)dp[i][sign] += dp[i-1][l];for (int l = sign + 2; l < n; l++)dp[i][sign] += dp[i-1][l];}}long long int ans = 0;for (int i = 0; i < n; i++)ans += dp[n-1][i];printf("%lld\n",ans);}return 0;
}

这篇关于UVA - 10401 Injured Queen Problem的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---