[UVA][dp] 910 - TV game
Problem F
TV game
Figure 1.1 - The carpet for one game.
The next TV game will be played by single players on a special kind of labyrinth. The player will step on a carpet with a drawing like the one in fig. 1.1, and wait on position A. Each position has two ways out, labeled by 0 and 1, which lead to the next position. To choose which way to take, the player must answer a question. If the answer is correct he takes the 1 way, otherwise the 0 way is followed. Of course, the answer may be deliberately wrong if the 0 way is sought for. The next position may be different or remain the same as before.
Some of the positions, indicated by a double circle, are special. If, exactly after a predetermined number of moves, the player gets on one of those special positions he wins, otherwise he loses.
In the example, if the total number of moves is m=2, failing the first question and passing the second, i. e. the sequence 01, directs the player to go from A, the start position, to B and then to C. It solves the problem, as C is a special position, in the sole possible way. In fact, 00 would lead to D and 10 and 11 to E, which are not special. In the case m=3, there is no solution. But in the case m=5, several solutions are available, for instance 01011, 01101 or 00011. Thus there are 3 out of 2^m = 32 ways to win, which gives an idea of the probability of winning just choosing the moves by tossing a coin.
Notice that should A also be a special position, there would be a way of scoring in zero moves.
Problem
The problem to be solved is, given a carpet and a number of moves m, to determine the number of different ways to score, i.e., to reach one of the special positions in exactly m moves, from the start position. The start position is the first position, labeled A. From each position there are exactly 2 ways out, labeled by the symbols 0 and 1.
Input
The input is a text file with one or more test cases, each of them containing several lines as follows.
The first line of the input contains the number N (integer format) of positions. The positions are labeled in alphabetic sequence, starting from A, and there are at most 26. The next N lines contain four characters each, separated by single spaces, where the first is the name of a position, the second the position the player reaches if he chooses the path labeled 0, the third the position the player reaches if he chooses the path labeled 1, and the fourth a 'x' if the position is special or a '-' if not.
The last line specifies m, the number of moves to be considered, 0 ≤ m ≤ 30.
Output
For each test case, the output consists of one line which contains one integer indicating the number of different ways to win. 0 means there are no solutions.
Sample Input
5 A B E - B D C - C D A x D D B - E E E - 5
Sample Output
3
Gabriel David, MIUP'2003
(Portuguese National ACM Programming Contest)
題目描述：
每次答題會有 0/1，然後轉移狀態，會有一些特別的點可以被 accept。
從 A 出發，問有幾中方法可以在 m 個問題之後，達到 accept。
題目解法：
做動態規劃, 將狀態進行轉移。
#include <stdio.h>
#include <string.h>
int main() {
int m, i, j;
while(scanf("%d", &m) == 1) {
int accept[26] = {};
int link[26][2] = {};
while(m--) {
char s1[2], s2[2], s3[2], s4[2];
scanf("%s %s %s %s", s1, s2, s3, s4);
link[s1[0]-'A'][0] = s2[0]-'A';
link[s1[0]-'A'][1] = s3[0]-'A';
if(s4[0] == 'x')
accept[s1[0]-'A'] = 1;
}
scanf("%d", &m);
int dp[35][26] = {}, flag = 0;
dp[0][0] = 1;
for(i = 0; i < m; i++) {
for(j = 0; j < 26; j++) {
dp[i+1][link[j][0]] += dp[i][j];
dp[i+1][link[j][1]] += dp[i][j];
}
}
int ret = 0;
for(i = 0; i < 26; i++)
ret += dp[m][i]*accept[i];
printf("%d\n", ret);
}
return 0;
}