UVa 10401 Injured Queen Problem(단순 DP)

제목:
부상당한 황후는 그 열과 그 주위의 9개의 칸만 공격할 수 있었다.
문자열을 지정합니다. 만약 i번째 문자가 있다면?황후는 임의의 위치에 놓을 수 있다는 뜻인데, 그렇지 않다면?어느 줄에 두어야 하는지를 지정하고 몇 가지 놓는 방법이 있는지 물어본다.
아이디어:
이런 칸의 제목은 샤오밍이 집에 돌아가는 것과 유사하다. 몇 가지 경로를 선택할 수 있지만 초기점과 끝 상태가 그다지 같지 않을 뿐이다.
dp[i, j]는 (i, j) 좌표를 최대 몇 가지 놓는 방법이 있음을 나타낸다. dp[i, j]는 dp[i-1, k]에 달려 있고 k는 제목 조건에 달려 있다.

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>



const int MAXN = 20;

char b[MAXN];

long long int dp[MAXN][MAXN];



int main()

{

    while (scanf("%s", b) == 1)

    {

        int n = strlen(b);

        memset(dp, 0, sizeof(dp));



        if (b[0] == '?')

        {

            for (int i = 0; i < n; ++i)

                dp[0][i] = 1;

        }

        else

        {

            if (isdigit(b[0]))

            {

                int k = b[0] - '1';

                dp[0][k] = 1;

            }

            else 

            {

                int k = b[0] - 'A' + 9;

                dp[0][k] = 1;

            }

        }



        for (int i = 1; i < n; ++i)

        {

            if (b[i] == '?')

            {

                for (int j = 0; j < n; ++j)

                {

                    for (int k = 0; k < j - 1; ++k)

                        dp[i][j] += dp[i-1][k];

                    for (int k = j + 2; k < n; ++k)

                        dp[i][j] += dp[i-1][k];

                }

            }

            else

            {

                int j;

                if (isdigit(b[i]))

                    j = b[i] - '1';

                else

                    j = b[i] - 'A' + 9;



                for (int k = 0; k < j - 1; ++k)

                    dp[i][j] += dp[i-1][k];

                for (int k = j + 2; k < n; ++k)

                    dp[i][j] += dp[i-1][k];

            }

        }

        long long int ans = 0;

        for (int i = 0; i < n; ++i)

            ans += dp[n-1][i];

        printf("%lld
", ans);

    }

    return 0;

}