c780: 106北二5.炮打眾卒遊戲

2019-09-16

內容

輸入

測試資料只有一行,有兩個數字 n 及 m,
表示棋盤大小為 n × m,
其中 1 ≤ n ≤ 8,1 ≤ m ≤ 8 且 n × m ≤ 42。
這兩個數字之間用空格(white space)隔開。

範例輸入一：
3 5

範例輸入二：
4 3

輸出

輸出資料為一個正整數,表示一開始在左上角的炮能吃到最多顆卒的數目。

範例輸出一：
7

範例輸出二：
5

解題思路

依照題意使用 DFS 列舉所有可能性後輸出最大值即可。

完整程式碼

AC (0.1s, 104KB)

#include <stdio.h>
#include <memory.h>

int n, m, best;
char table[10][10];

void serch(int x, int y, int cont)
{
    if (cont > best)
        best = cont;
    int i;
    table[x][y] = 0;
    for (i = x + 1; i < n && !table[i][y]; ++i)
        ;
    while (++i < n)
    {
        if (table[i][y])
        {
            serch(i, y, cont + 1); break;
        }
    }
    for (i = x - 1; ~i && !table[i][y]; --i)
        ;
    while (--i >= 0)
    {
        if (table[i][y])
        {
            serch(i, y, cont + 1); break;
        }
    }
    for (i = y + 1; i < m && !table[x][i]; ++i)
        ;
    while (++i < m)
    {
        if (table[x][i])
        {
            serch(x, i, cont + 1); break;
        }
    }
    for (i = y - 1; ~i && !table[x][i]; --i)
        ;
    while (--i >= 0)
    {
        if (table[x][i])
        {
            serch(x, i, cont + 1); break;
        }
    }
    table[x][y] = 1;
}

int main()
{
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < n; ++i)
        memset(table[i], 1, m);
    serch(0, 0, 0);
    printf("%d\n", best);
    return 0;
}