求网格中的黑点分布

匿名网友 匿名网友 发布于: 2015-08-30 00:00:00
阅读 104 收藏 0 点赞 0 评论 0

求网格中的黑点分布。现有6*7的网格,在某些格子中有黑点,已知各行与各列中有黑点的点数之和,请在这张网格中画出黑点的位置。(这是一网友提出的题目,说是他笔试时遇到算法题)
#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;
int iSumR[ROWS], iSumC[COLS], Grid[ROWS][COLS];

int Set(int iRowNo) {
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 {
        for(int iColNo=0; iColNo < COLS; iColNo++) {
            if(iPointsR[iRowNo] == 0) {
                Set(iRowNo + 1);
   } else if(Grid[iRowNo][iColNo]==0) {
Grid[iRowNo][iColNo] = 1;
iSumR[iRowNo]++; iSumC[iColNo]++;                                  if(iSumR[iRowNo]<iPointsR[iRowNo] && iSumC[iColNo]<=iPointsC[iColNo])
                     Set(iRowNo);
else if(iSumR[iRowNo]==iPointsR[iRowNo] && iRowNo < ROWS)
                     Set(iRowNo + 1);
                Grid[iRowNo][iColNo] = 0;
                iSumR[iRowNo]–;
iSumC[iColNo]–;
            }
        }
    }
return iFound;     // 用于判断是否有解
}
int main(int argc, char* argv[]) {
    if(!Set(0))
        printf(“Failure!”);
}

评论列表
文章目录