首页 > 代码库 > uva10401Injured Queen Problem(递推)
uva10401Injured Queen Problem(递推)
题目:uva10401Injured Queen Problem(递推)
题目大意:依旧是在棋盘上放皇后的问题,这些皇后是受伤的皇后,攻击范围缩小了。攻击范围在图中用阴影表示(题目)。然后给出棋盘的现状,???3?4:在一个6*6的棋盘上,因为皇后是可以列向攻击的,所以一列只能放一个皇后,所以第一个?代表第一列的皇后放的行未知,这样3的意思就是第4列皇后在第三行,也就是确定了第4列皇后的位置。要求棋盘上的皇后不互相攻击,问这样的棋盘可以有多少不同的放法。
解题思路:一开始想状态,想把不同的棋盘作为状态,但是发现这样的状态太多了。后面才发现因为是求总共的数目,那么在放第i个皇后的时候,其实前面的i - 1个皇后我们只需要知道有多少种放法就可以,并不需要将i - 1个皇后在棋盘上不同的情况都记录下来。根据皇后的攻击范围写出状态方程:d【i】【j】代表第i列的皇后放在第j行。d【i】【j】 = sum (d【i - 1】【k】)
k >= 0 && k < n(棋盘的行或列) && abs (k - j ) > 1.
代码:
#include <cstdio> #include <cstring> #include <cstdlib> typedef long long ll; const int N = 20; ll dp[N][N]; char str[N]; int len; void init () { memset (dp, 0, sizeof (dp)); for (int i = 0; i < len; i++) dp[0][i] = 1; } int translate (int i) { if (str[i] >= '1' && str[i] <= '9') return str[i] - '1'; else { switch (str[i]) { case 'A' : return 9; case 'B' : return 10; case 'C' : return 11; case 'D' : return 12; case 'E' : return 13; case 'F' : return 14; } } } void handle (int i, int j) { for (int k = 0; k < len; k++) { if (abs (k - j) > 1) dp[i][j] += dp[i - 1][k]; } } int main () { while (scanf ("%s" , str) != EOF) { len = strlen (str); init (); for (int i = 1; i < len; i++) { if (str[i - 1] == '?') { for (int j = 0; j < len; j++) handle(i, j); } else { int k = translate (i - 1); for (int j = 0; j < len; j++) { if (abs (j - k) > 1) dp[i][j] += dp[i - 1][k]; } } } ll ans; if (str[len - 1] != '?') ans = dp[len - 1][translate(len - 1)]; else { ans = 0; for (int i = 0; i < len; i++) ans += dp[len - 1][i]; } printf ("%lld\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。