蓝桥杯 第三届C/C++预赛真题(7) 放棋子(水题)

今有 6 x 6 的棋盘格。其中某些格子已经预先放好了棋子。现在要再放上去一些,使得:每行每列都正好有3颗棋子。我们希望推算出所有可能的放法。下面的代码就实现了这个功能。

初始数组中,“1”表示放有棋子,“0”表示空白。

蓝桥杯 第三届C/C++预赛真题(7) 放棋子(水题)
  1 int N = 0;
  2 
  3 bool CheckStoneNum(int x[][6])
  4 {
  5     for(int k=0; k<6; k++)
  6     {
  7         int NumRow = 0;
  8         int NumCol = 0;
  9         for(int i=0; i<6; i++)
 10         {
 11             if(x[k][i]) NumRow++;
 12             if(x[i][k]) NumCol++;
 13         }
 14         if(_____________________) return false;  // 填空
 15     }
 16     return true;
 17 }
 18 
 19 int GetRowStoneNum(int x[][6], int r)
 20 {
 21     int sum = 0;
 22     for(int i=0; i<6; i++)     if(x[r][i]) sum++;
 23     return sum;
 24 }
 25 
 26 int GetColStoneNum(int x[][6], int c)
 27 {
 28     int sum = 0;
 29     for(int i=0; i<6; i++)     if(x[i][c]) sum++;
 30     return sum;
 31 }
 32 
 33 void show(int x[][6])
 34 {
 35     for(int i=0; i<6; i++)
 36     {
 37         for(int j=0; j<6; j++) printf("%2d", x[i][j]);
 38         printf("\n");
 39     }
 40     printf("\n");
 41 }
 42 
 43 void f(int x[][6], int r, int c);
 44 
 45 void GoNext(int x[][6],  int r,  int c)
 46 {
 47     if(c<6)
 48         _______________________;   // 填空
 49     else
 50         f(x, r+1, 0);
 51 }
 52 
 53 void f(int x[][6], int r, int c)
 54 {
 55     if(r==6)
 56     {
 57         if(CheckStoneNum(x))
 58         {
 59             N++;
 60             show(x);
 61         }
 62         return;
 63     }
 64 
 65     if(______________)  // 已经放有了棋子
 66     {
 67         GoNext(x,r,c);
 68         return;
 69     }
 70     
 71     int rr = GetRowStoneNum(x,r);
 72     int cc = GetColStoneNum(x,c);
 73 
 74     if(cc>=3)  // 本列已满
 75         GoNext(x,r,c);  
 76     else if(rr>=3)  // 本行已满
 77         f(x, r+1, 0);   
 78     else
 79     {
 80         x[r][c] = 1;
 81         GoNext(x,r,c);
 82         x[r][c] = 0;
 83         
 84         if(!(3-rr >= 6-c || 3-cc >= 6-r))  // 本行或本列严重缺子,则本格不能空着!
 85             GoNext(x,r,c);  
 86     }
 87 }
 88 
 89 int main(int argc, char* argv[])
 90 {
 91     int x[6][6] = {
 92         {1,0,0,0,0,0},
 93         {0,0,1,0,1,0},
 94         {0,0,1,1,0,1},
 95         {0,1,0,0,1,0},
 96         {0,0,0,1,0,0},
 97         {1,0,1,0,0,1}
 98     };
 99 
100     f(x, 0, 0);
101     
102     printf("%d\n", N);
103 
104     return 0;
105 }
蓝桥杯 第三届C/C++预赛真题(7) 放棋子(水题)

请分析代码逻辑,并推测划线处的代码。

答案写在 “解答.txt” 文件中

注意:只写划线处应该填的内容,划线前后的内容不要抄写。


 

  解答

  NumRow!=3 || NumCol!=3
  f(x,r,c+1)
  x[r][c]==1

  测试代码

蓝桥杯 第三届C/C++预赛真题(7) 放棋子(水题)
  1 #include <stdio.h>
  2 
  3 int N = 0;
  4 
  5 bool CheckStoneNum(int x[][6])
  6 {
  7     for(int k=0; k<6; k++)
  8     {
  9         int NumRow = 0;
 10         int NumCol = 0;
 11         for(int i=0; i<6; i++)
 12         {
 13             if(x[k][i]) NumRow++;
 14             if(x[i][k]) NumCol++;
 15         }
 16         if(NumRow!=3 || NumCol!=3) return false;  // 填空
 17     }
 18     return true;
 19 }
 20 
 21 int GetRowStoneNum(int x[][6], int r)
 22 {
 23     int sum = 0;
 24     for(int i=0; i<6; i++)     if(x[r][i]) sum++;
 25     return sum;
 26 }
 27 
 28 int GetColStoneNum(int x[][6], int c)
 29 {
 30     int sum = 0;
 31     for(int i=0; i<6; i++)     if(x[i][c]) sum++;
 32     return sum;
 33 }
 34 
 35 void show(int x[][6])
 36 {
 37     for(int i=0; i<6; i++)
 38     {
 39         for(int j=0; j<6; j++) printf("%2d", x[i][j]);
 40         printf("\n");
 41     }
 42     printf("\n");
 43 }
 44 
 45 void f(int x[][6], int r, int c);
 46 
 47 void GoNext(int x[][6],  int r,  int c)
 48 {
 49     if(c<6)
 50         f(x,r,c+1);   // 填空
 51     else
 52         f(x, r+1, 0);
 53 }
 54 
 55 void f(int x[][6], int r, int c)
 56 {
 57     if(r==6)
 58     {
 59         if(CheckStoneNum(x))
 60         {
 61             N++;
 62             show(x);
 63         }
 64         return;
 65     }
 66 
 67     if(x[r][c]==1)  // 已经放有了棋子
 68     {
 69         GoNext(x,r,c);
 70         return;
 71     }
 72     
 73     int rr = GetRowStoneNum(x,r);
 74     int cc = GetColStoneNum(x,c);
 75 
 76     if(cc>=3)  // 本列已满
 77         GoNext(x,r,c);  
 78     else if(rr>=3)  // 本行已满
 79         f(x, r+1, 0);   
 80     else
 81     {
 82         x[r][c] = 1;
 83         GoNext(x,r,c);
 84         x[r][c] = 0;
 85         
 86         if(!(3-rr >= 6-c || 3-cc >= 6-r))  // 本行或本列严重缺子,则本格不能空着!
 87             GoNext(x,r,c);  
 88     }
 89 }
 90 
 91 int main(int argc, char* argv[])
 92 {
 93     int x[6][6] = {
 94         {1,0,0,0,0,0},
 95         {0,0,1,0,1,0},
 96         {0,0,1,1,0,1},
 97         {0,1,0,0,1,0},
 98         {0,0,0,1,0,0},
 99         {1,0,1,0,0,1}
100     };
101 
102     f(x, 0, 0);
103     
104     printf("%d\n", N);
105 
106     return 0;
107 }
蓝桥杯 第三届C/C++预赛真题(7) 放棋子(水题)

 

Freecode : www.cnblogs.com/yym2013

蓝桥杯 第三届C/C++预赛真题(7) 放棋子(水题),布布扣,bubuko.com

蓝桥杯 第三届C/C++预赛真题(7) 放棋子(水题)

上一篇:Java 舍入模式 数字的格式化


下一篇:下载python标准库--python