坏巧克力问题.doc

//巧克力大小 #define M 8 #define N 8 //设置坏巧克力块的位置 #define X 4 #define Y 4 void print(char cho[M][N]) { //打印出巧克力形状 for(int i=0;iM;i++) { for(int j=0;jN;j++) printf(%d ,cho[i][j]); printf(\n); } } //执行掰巧克力的函数 void Execute(char cho[M][N],char pos,int index) { //掰下一列 if(pos==C || pos==c) { for(int i=0;iM;i++) { for(int j=0;jN;j++) if(j==index)cho[i][j]=3; } } //掰下一行 else if(pos==R || pos==r) { for(int i=0;iM;i++) { if(i==index) { for(int j=0;jN;j++)cho[i][j]=3; } } } } //分析行，给出决策可以掰那些行 void Row(char cho[M][N],char dm[]) { for(int i=0;iM;i++) { int s=-1; //去掉坏巧克力所在行 if(i!=X) { for(int j=0;jN;j++) { if(cho[i][j]!=3)s=1; } } dm[i]=s; } } //分析列，给出决策可以掰那些列 void Col(char cho[M][N],char dm[]) { for(int j=0;jN;j++) { int s=-1; //去掉坏巧克力所在列 if(j!=Y) { for(int i=0;iM;i++) { if(cho[i][j]!=3)s=1; } } dm[j]=s; } } //预处理，计算机模拟执行掰的过程，然后计算剩余步骤 int PreDispose(char cho[M][N],char dm[]) { int cnt=0; //巧克力块的副本 char cho_t[M][N]; //可以掰的行标，用1表示 char row[M]; //可以掰的列表，用1表示 char col[N]; memset(row,-1,M);memset(col,-1,N); memcpy(cho_t,cho,M*N); Execute(cho_t,dm[0],dm[1]); //分析行，给出决策 Row(cho,row); //分析列，给出决策 Col(cho,col); for(int i=0;iM;i++) if(row[i]!=-1)cnt++; for(int j=0;jN;j++) if(col[j]!=-1)cnt++; return cnt; } //分析现在的巧克力,并给出决策，掰哪一块 void Alaysize(char cho[M][N],char dm[2]) { //可以掰的行标，用1表示 char row[M]; //可以掰的列表，用1表示 char col[N]; memset(row,-1,M);memset(col,-1,N); //分析行，给出决策 Row(cho,row); //分析列，给出决策 Col(cho,col); //进行预处理，判断执行后的剩余次数,找到一个剩余次数为奇数的步骤执行 for(int i=M-1;i=0;i--) { if(row[i] != -1)