Poj2488_深度優先検索+遡及

#define LOCAL
#include
#include 

const int movex[10] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int movey[10] = {-1, 1, -2, 2, -2, 2, -1, 1};
const char Letter[20] = {'1', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'};
int p, q;
int match[30][30];
int last[50][2];
bool flag = false;
int kase;

bool dfs(int x, int y, int lx, int ly)
{
    if (flag == true)
        return false;
    match[x][y] = 1;
    int countt = 0;
    for (int f = 1; f <= q; f++)
    {
        for (int g = 1; g <= p; g++)
        {
            countt += match[f][g];
        }
    }
    last[countt][0] = lx;
    last[countt][1] = ly;
    if (countt == p * q)
    {
        flag = true;
        printf("Scenario #%d:
", kase);
        for (int c = 2; c <= countt; c++)
        {
            printf("%c%d", Letter[last[c][0]], last[c][1]);
        }
        printf("%c%d", Letter[x], y);
        printf("

");
        return true;
    }

    for (int w = 0; w <= 7; w++)
    {
        int tx = x + movex[w];
        int ty = y + movey[w];
        if (tx <= q && tx >= 1 && ty <= p && ty >= 1 && match[tx][ty] != 1)
        {
            if(dfs(tx, ty, x, y))
                return true;
        }
    }
    match[x][y] = 0;
    return false;
}
int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &p, &q);
        kase = i;
        flag = false;

        memset(match, 0, sizeof(match));
        memset(last, 0, sizeof(last));
        dfs(1, 1, 0, 0);

        if (flag == false)
            printf("Scenario #%d:
impossible

", kase);
    }

    return 0;
}