Шатрын самбар дээр тэмээ байрлуулах¶

Аль ч хоёр тэмээ бие бие рүүгээ довтлохгүй байхаар $N \times N$ шатрын самбар дээр $K$ тэмээ байрлуулах аргын тоог ол.

Алгоритм¶

Энэ бодлогыг динамик программчлал ашиглан бодож болно.

Шатрын самбарын диагональуудыг дараах байдлаар дугаарлая: хар диагональууд сондгой индекстэй, цагаан диагональууд тэгш индекстэй, диагональуудыг доторх нүдний тооны буурахгүй дарааллаар дугаарлана. $5 \times 5$ шатрын самбарын жишээ энд байна.

$$\begin{matrix} \bf{1} & 2 & \bf{5} & 6 & \bf{9} \\\ 2 & \bf{5} & 6 & \bf{9} & 8 \\\ \bf{5} & 6 & \bf{9} & 8 & \bf{7} \\\ 6 & \bf{9} & 8 & \bf{7} & 4 \\\ \bf{9} & 8 & \bf{7} & 4 & \bf{3} \\\ \end{matrix}$$

D[i][j] нь i диагональтай ижил өнгөтэй, i хүртэлх индекстэй диагональууд дээр j тэмээ байрлуулах аргын тоог тэмдэглэе. Тэгвэл i = 1...2N-1 ба j = 0...K.

Бид D[i][j]-г зөвхөн D[i-2]-ийн утгуудыг ашиглан тооцоолж болно (бид $i$-тэй ижил өнгөтэй диагональуудыг л авч үздэг тул 2-ыг хасна). D[i][j]-г олох хоёр арга бий. Эсвэл бид бүх j тэмээг өмнөх диагональууд дээр байрлуулна: тэгвэл үүнд хүрэх D[i-2][j] арга байна. Эсвэл бид нэг тэмээг i диагональ дээр, j-1 тэмээг өмнөх диагональууд дээр байрлуулна. Үүнийг хийх аргын тоо нь i диагональ дахь нүдний тооноос j-1-г хассантай тэнцүү, учир нь өмнөх диагональууд дээр байрлуулсан j-1 тэмээ тус бүр одоогийн диагональ дээр нэг нүд хаана. i диагональ дахь нүдний тоог дараах байдлаар тооцоолж болно:

int squares (int i) {
    if (i & 1)
        return i / 4 * 2 + 1;
    else
        return (i - 1) / 4 * 2 + 2;
}

Суурь тохиолдол энгийн: D[i][0] = 1, D[1][1] = 1.

D[i][j]-ийн бүх утгыг тооцоолсны дараа хариуг дараах байдлаар олж болно: хар диагональууд дээр байрлуулсан тэмээний бүх боломжит тоо i=0...K-г, харгалзах цагаан диагональууд дээрх тэмээний тоо K-i-тэй авч үзье. Хар ба цагаан диагональууд дээр байрлуулсан тэмээ хэзээ ч бие бие рүүгээ довтлохгүй тул байршуулалтыг бие даан хийж болно. Сүүлийн хар диагоналийн индекс нь 2N-1, сүүлийн цагаанынх нь 2N-2. i бүрийн хувьд бид хариуд D[2N-1][i] * D[2N-2][K-i]-г нэмнэ.

Implementation¶

int bishop_placements(int N, int K)
{
    if (K > 2 * N - 1)
        return 0;

    vector<vector<int>> D(N * 2, vector<int>(K + 1));
    for (int i = 0; i < N * 2; ++i)
        D[i][0] = 1;
    D[1][1] = 1;
    for (int i = 2; i < N * 2; ++i)
        for (int j = 1; j <= K; ++j)
            D[i][j] = D[i-2][j] + D[i-2][j-1] * (squares(i) - j + 1);

    int ans = 0;
    for (int i = 0; i <= K; ++i)
        ans += D[N*2-1][i] * D[N*2-2][K-i];
    return ans;
}