修正网上关于“网格中的黑点分布”算法

求网格中的黑点分布

现有6*7的网格，在某些格子中有黑点，已知各行与各列中有黑点的点数之和，请在这张网格中画出黑点的位置。

网上很容易搜到代码，可是我运行后发现会出现死循环或者出现重复结果的情况。

我修改了一下，感觉没什么问题了....

如果有人发现还有问题，劳烦留言~~

说明：

1、set的第二个参数是为了区分是否是同一行的set（）调用，-1表示非同行调用；

2、后面代码蓝色部分是修改内容。

#include "stdafx.h"
#include <windows.h>

#define ROWS 6
#define COLS 7
int iPointsR[ROWS] = {2, 0, 4, 3, 4, 0}; // 各行黑点数和的情况
int iPointsC[COLS] = {4, 1, 2, 2, 1, 2, 1}; // 各列黑点数和的情况
int iCount, iFound = 0;
int iSumR[ROWS], iSumC[COLS], Grid[ROWS][COLS];

int Set(int iRowNo,int iParentColNo) {
    if(iRowNo == ROWS) {
        for(int iColNo=0; iColNo < COLS && iSumC[iColNo]==iPointsC[iColNo]; iColNo++)
            if(iColNo == COLS-1) {
                printf("\nNo.%d:\n", ++iCount);
                for(int i=0; i < ROWS; i++)
                    for(int j=0; j < COLS; j++)
                        printf("%d%c", Grid[i][j], (j+1) % COLS ? ' ' : '\n');
                iFound = 1;    // iFound = 1
             }
    } else {
        int iColNo = 0;
        if(iParentColNo != -1) iColNo = iParentColNo + 1;
        for(; iColNo < COLS; iColNo++) {
            if(iPointsR[iRowNo] == 0 && iColNo == 0) {
                 Set(iRowNo + 1,-1);
            }else if(Grid[iRowNo][iColNo]==0) {
                Grid[iRowNo][iColNo] = 1;
                iSumR[iRowNo]++; iSumC[iColNo]++;
                if(iSumR[iRowNo]<iPointsR[iRowNo] && iSumC[iColNo]<=iPointsC[iColNo] && iColNo != COLS - 1)
                    Set(iRowNo,iColNo);
                else if(iSumR[iRowNo]==iPointsR[iRowNo] && iRowNo < ROWS)
                    Set(iRowNo + 1,-1);
                Grid[iRowNo][iColNo] = 0;
                iSumR[iRowNo]--;
                iSumC[iColNo]--;
            }
        }
    }
    return iFound; // 用于判断是否有解
}
    int main(int argc, char* argv[]) {
        if(!Set(0,-1))
            printf("Failure!");
        system("pause");
    }

#############################################################################################

去掉行号，方便大家复制

#include "stdafx.h"

#include

#define ROWS 6

#define COLS 7

int iPointsR[ROWS] = {2, 0, 4, 3, 4, 0};           // 各行黑点数和的情况

int iPointsC[COLS] = {4, 1, 2, 2, 1, 2, 1};        // 各列黑点数和的情况

int iCount, iFound = 0;

int iSumR[ROWS], iSumC[COLS], Grid[ROWS][COLS];

int Set(int iRowNo,int iParentColNo) {

    if(iRowNo == ROWS) {

        for(int iColNo=0; iColNo < COLS && iSumC[iColNo]==iPointsC[iColNo]; iColNo++)

            if(iColNo == COLS-1) {

                printf("\nNo.%d:\n", ++iCount);

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

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

                        printf("%d%c", Grid[i][j], (j+1) % COLS ? ' ' : '\n');

                iFound = 1; // iFound = 1

             }

    } else {

int iColNo = 0;

if(iParentColNo != -1) iColNo = iParentColNo + 1;

        for(; iColNo < COLS; iColNo++) {

            if(iPointsR[iRowNo] == 0 && iColNo == 0) {

                 Set(iRowNo + 1,-1);

            }else if(Grid[iRowNo][iColNo]==0) {

                Grid[iRowNo][iColNo] = 1;

                iSumR[iRowNo]++; iSumC[iColNo]++;

                if(iSumR[iRowNo] && iColNo != COLS - 1)

                    Set(iRowNo,iColNo);

else if(iSumR[iRowNo]==iPointsR[iRowNo] && iRowNo < ROWS)

                    Set(iRowNo + 1,-1);

Grid[iRowNo][iColNo] = 0;

iSumR[iRowNo]--;

iSumC[iColNo]--;

            }

        }

    }

    return iFound;      // 用于判断是否有解

}

    int main(int argc, char* argv[]) {

        if(!Set(0,-1))

            printf("Failure!");

system("pause");

    }