排球队员站位有关问题

本题适合来理解回溯的思想：

代码给出，不做过多解释：

#include <iostream> using namespace std; int main() { int positionCan[6][6];/*运动员对于某个位置能不能站，0代表能，1代表能*/ int position[6];/*运动员的最终站位*/ int judge[6];//判断某个位置是否已经有人,1代表有人，0代表无人 for (int i=0;i<6;i++)//运动员编号 { for (int j = 0;j<6;j++)//位置编号 { if (i == j) { positionCan[i][j] = 0; } else { positionCan[i][j] = 1; } } } for (int i=0;i<6;i++) { judge[i] = 0;//初始为0 } for (int i=0;i<6;i++) { position[i] = -1;//刚开始，所有运动员都没有位置站 } positionCan[0][4] = 0;//1号队员不在后排 positionCan[0][5] = 0;//1号队员不在后排 positionCan[1][4] = 0;//2号队员不是二传手 positionCan[2][1] = 0;//3号队员不是二传手 positionCan[2][4] = 0;//3号队员不是二传手 positionCan[4][2] = 0;//5号队员不是副攻手 positionCan[4][5] = 0;//5号队员不是副攻手 positionCan[5][2] = 0;//6号队员不是副攻手 positionCan[5][0] = 0;//6号队员不能站后排 positionCan[5][4] = 0;//6号队员不能站后排 int i=0,; int j=0; while (i<6) { j = 0; while (j<6) { if (i==3)//第四位运动员和第三位运动员不能在同一排 { if (position[2] == 3)//如果3号队员站到了4号位（即唯一的前排可能）,则4号队员应站后排 { positionCan[3][1] = 0; positionCan[3][2] = 0; positionCan[3][3] = 0; } else { positionCan[3][0] = 0; positionCan[3][4] = 0; positionCan[3][5] = 0; } } else//如果回溯的话，需要对第四位队员进行恢复，否则会发生错误，因为它的站位限制不固定 { for (int k=0;k<6;k++) { if (k!=3) { positionCan[3][k] = 1; } } } //可以站J号位，且此位无人 if (positionCan[i][j] == 1 && judge[j] == 0) { judge[j] = 1;//i号运动员站j号位 position[i] = j;//i号运动员站j号位 i++; break; } else { j++; } while (j==6)//如果i号运动员没有找到可站的位置,则回溯 { i--; j = position[i] + 1; judge[position[i]] = 0;//没有位置站 position[i] = -1;//前一名运动员重新回到没有位置站的情况 } } } for (int k = 0;k<6;k++) { cout<<"第"<<k+1<<"号队员的站位是："<<position[k]+1<<endl; } return 0; }
运行结果：