#include<stdio.h>
#include<stdlib.h>

#define ChessBoardScale 8                        //棋盘规模;
int Record[ChessBoardScale][ChessBoardScale];   //记录被吃几率；
char Cover[ChessBoardScale][ChessBoardScale];   //记录可以放马的位置；

void GetChance();                            //计算每一个位置被其它位置的马吃掉的几率；
void ReCaculateChance();   //主题算法：计算极小覆盖；
void GetMinCover();            //输出最终结果；
void Condition(int a, int b);               //被吃几率的再次计算；

//计算每一个位置被其它位置的马吃掉的几率
void GetChance(){
    for (int i=0;i<ChessBoardScale;i++){
        for (int j = 0; j < ChessBoardScale; j++){
            int k = 0;
            if (j - 2 >= 0 && i - 1 >= 0){ Record[i - 1][j - 2]++; }
            if (j - 1 >= 0 && i - 2 >= 0){ Record[i - 2][j - 1]++; }
            if (j - 2 >= 0 && i + 1 < ChessBoardScale){ Record[i + 1][j - 2]++; }
            if (j - 1 >= 0 && i + 2 < ChessBoardScale){ Record[i + 2][j - 1]++; }
            if (j + 2 < ChessBoardScale  &&  i - 1 >= 0){ Record[i - 1][j + 2]++; }
            if (j + 1 < ChessBoardScale  &&  i - 2 >= 0){ Record[i - 2][j + 1]++; }
            if (j + 2 < ChessBoardScale  &&  i + 1 < ChessBoardScale){ Record[i + 1][j + 2]++; }
            if (j + 1 < ChessBoardScale  &&  i + 2 < ChessBoardScale){ Record[i + 2][j + 1]++; }
        }
    }
}

//主体算法
void ReCaculateChance(){
    int Max = Record[0][0];
    int Max_i = 0, Max_j = 0;
    //计算棋盘中被吃几率最大的位置；
    for (int i = 0; i < ChessBoardScale; i++){
        for (int j = 0; j < ChessBoardScale; j++){
            if (Record[i][j] > Max){
                Max = Record[i][j];
                Max_i = i;
                Max_j = j;
            }
        }
    }
    //在棋盘中被吃几率最大的位置放马；
    if (Record[Max_i][Max_j] >= 0){
        Cover[Max_i][Max_j] = '@';
        Record[Max_i][Max_j] = -1;
        printf("\n此步计算马应该在的位置：%d \n", (ChessBoardScale*Max_i + Max_j)); //输出马应该在的位置；
    }

    //极小覆盖的算法
    if (Max_j - 2 >= 0 && Max_i - 1 >= 0){
        Record[Max_i - 1][Max_j - 2] = -1; int i = Max_i - 1; int j = Max_j - 2;
        Condition(i, j);
    }
    if (Max_j - 1 >= 0 && Max_i - 2 >= 0){
        Record[Max_i - 2][Max_j - 1] = -1; int i = Max_i - 2; int j = Max_j - 1;
        Condition(i, j);
    }
    if (Max_j - 2 >= 0 && Max_i + 1<ChessBoardScale){
        Record[Max_i + 1][Max_j - 2] = -1; int i = Max_i + 1; int j = Max_j - 2;
        Condition(i, j);
    }
    if (Max_j - 1 >= 0 && Max_i + 2<ChessBoardScale){
        Record[Max_i + 2][Max_j - 1] = -1; int i = Max_i + 2; int j = Max_j - 1;
        Condition(i, j);
    }
    if (Max_j + 2<ChessBoardScale && Max_i - 1 >= 0){
        Record[Max_i - 1][Max_j + 2] = -1; int i = Max_i - 1; int j = Max_j + 2;
        Condition(i, j);
    }
    if (Max_j + 1<ChessBoardScale && Max_i - 2 >= 0){
        Record[Max_i - 2][Max_j + 1] = -1; int i = Max_i - 2; int j = Max_j + 1;
        Condition(i, j);
    }
    if (Max_j + 2<ChessBoardScale && Max_i + 1<ChessBoardScale){
        Record[Max_i + 1][Max_j + 2] = -1; int i = Max_i + 1; int j = Max_j + 2;
        Condition(i, j);
    }
    if (Max_j + 1<ChessBoardScale && Max_i + 2<ChessBoardScale){
        Record[Max_i + 2][Max_j + 1] = -1; int i = Max_i + 2; int j = Max_j + 1;
        Condition(i, j);
    }

    //是否每一步都输出棋盘布局
    //----------------------------------------------------------------------------------------------
    //printf("棋盘的布局为：----------------------------------------------------------------\n");
    //int k9 = 0;
    //for (int i9 = 0; i9 < ChessBoardScale; i9++){
    //    for (int j9 = 0; j9 < ChessBoardScale; j9++){
    //        printf("[ %-2d ] ", k9);
    //        k9++;
    //    }
    //    printf("\n\n\n");
    //}

    printf("每次的覆盖情况------------------------------------------------------------------\n");
    for (int i2 = 0; i2 < ChessBoardScale; i2++){
        for (int j2 = 0; j2 < ChessBoardScale; j2++){
            printf("[ %c ] ", Cover[i2][j2]);
        }
        printf("\n\n\n\n");
    }
    printf("每个位置是否被吃掉（-1为被吃掉）:\n");
    for (int i3 = 0; i3 < ChessBoardScale; i3++){
        for (int j3 = 0; j3 < ChessBoardScale; j3++){
            printf("[ %-2d ] ", Record[i3][j3]); //输出的为每次每个位置被吃的几率；
        }
        printf("\n\n\n");
    }
}

//输出最终结果
void GetMinCover(){
    int Max_Record = 0;
    while (Max_Record != -1/**/){
        ReCaculateChance();                //循环计算最小覆盖；
        Max_Record = -1.5;               //中间变量；判断是否已完成最小覆盖的计算；
        for (int i = 0; i < ChessBoardScale; i++){
            for (int j = 0; j < ChessBoardScale; j++){
                if (Record[i][j] >= Max_Record){
                    Max_Record = Record[i][j];
                }
            }
        }
    }
}

//被吃几率的再次计算；
void Condition(int a, int b){
    if (b - 2 >= 0 && a - 1 >= 0 && Record[a - 1][b - 2] != -1 && Record[a - 1][b - 2] != 0){ Record[a - 1][b - 2]--; }
    if (b - 1 >= 0 && a - 2 >= 0 && Record[a - 2][b - 1] != -1 && Record[a - 2][b - 1] != 0){ Record[a - 2][b - 1]--; }
    if (b - 2 >= 0 && a + 1<ChessBoardScale && Record[a + 1][b - 2] != -1 && Record[a + 1][b - 2] != 0){ Record[a + 1][b - 2]--; }
    if (b - 1 >= 0 && a + 2<ChessBoardScale && Record[a + 2][b - 1] != -1 && Record[a + 2][b - 1] != 0){ Record[a + 2][b - 1]--; }
    if (b + 2 < ChessBoardScale && a - 1 >= 0 && Record[a - 1][b + 2] != -1 && Record[a - 1][b + 2] != 0){ Record[a - 1][b + 2]--; }
    if (b + 1 < ChessBoardScale && a - 2 >= 0 && Record[a - 2][b + 1] != -1 && Record[a - 2][b + 1] != 0){ Record[a - 2][b + 1]--; }
    if (b + 2 < ChessBoardScale && a + 1 < ChessBoardScale && Record[a + 1][b + 2] != -1 && Record[a + 1][b + 2] != 0){ Record[a + 1][b + 2]--; }
    if (b + 1 < ChessBoardScale && a + 2 < ChessBoardScale && Record[a + 2][b + 1] != -1 && Record[a + 2][b + 1] != 0){ Record[a + 2][b + 1]--; }
}

int main(){
    printf("棋盘的布局为：\n");
    int k = 0;
    for (int i = 0; i < ChessBoardScale; i++){
        for (int j = 0; j < ChessBoardScale; j++){
            printf("[ %-2d ] ", k);
            k++;
        }
        printf("\n\n");
    }

    printf("--------------------------------------------------------------------------------\n");
    GetChance();
    for (int m = 0; m < ChessBoardScale; m++){
        for (int n = 0; n < ChessBoardScale; n++){
            printf("%-2d ", Record[m][n]);
        }
        printf("\n");
    }
    printf("================================================================================\n\n");
    GetMinCover();
    printf("\n");

    system("pause");
    return 0;
}