排列组合与回溯法

排列，组合，回溯法

ex.1

/*
*  打印出一个字符串的全部排列。
*/
void permutation(char * str, char *pBegin) {
    if(*pBegin == '\0') {
        printf("%s,",str);
    } else {
        for(char *pCh = pBegin;pCh != '\0';++pCh){
          swap(pCh,pBegin);
            permutation(str,pBegin+1);
            swap(pCh,pBegin);
        }
    }
}

ex.2

/*
*  打印出一个字符串的组合。
*/

排列

• 全排列：从第一个数字起，每个数字分别与它后面的数字交换
• 去重全排列：从第一个数字起，每个数组分别与它后面非重复出现的数字交换

组合

• 基于递归
• 基于位图

ex.3

/*
*  输入一个含有8个数字的数组，判断有没有可能把这8个数字分配放到正方体
*  的8个顶点上，是得正方体上三组相对的面上的4个顶点的和都相等
*/
//求8个数字的全部排列，然后判断排列是否满足题目给出的条件

ex.4

/*
*  8皇后问题。在8*8的棋盘上拜放8个皇后，使其不能相互攻击，即8个皇后
*  不能处于同一行，同一列或者同一对角线上。
*/
//初始化一个columnIndex[8]数组，第i个数表示位于第i行的列数，因此用0-7来
//初始化数组，然后做全排列，逐个判断是否满足不同行、列、对角线的要求



//初始化一个columnIndex[8]数组，第i个数表示位于第i行的列数
// 使用回溯法，从第一行第一列初始化数组

回溯法

//8皇后
int C[8] = {0};
cout << search(0)  << endl；
 int tot = 0;
void search(int cur) {
    if(cur == 8) tot++;
    else for (int i = 0; i < 8;++i) {
        int ok = 1;
        C[cur] = i;
        for(int j = 0; j< cur; ++j) {
            if(C[cur]==C[j] || cur-C[cur]==j-C[j] || cur+C[cur]==j+C[j]){
              of = 0; break;  
          }
        }
        if(ok)  search(cur+1);
    }
}

//矩阵中的路径
//从任意格子出发，检查是否满足路径，同数组表示访问的路径表示已经到达过的位置以及当前到达的位置
//先检查当前格子，是否满足条件，满足则向另外4个方向出发，不满足则返回
   bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(matrix == NULL || rows < 1 || cols < 1 || str == NULL)
            return false;
        bool *visited= new bool[rows * cols];
        memset(visited, 0, rows*cols*sizeof(bool));
        
        int pathLength = 0;
        for(int row = 0;row < rows;++row) {
            for(int col = 0;col < cols;++col) {
                if(hasPathCore(matrix,rows,cols,row,col,str,pathLength,visited)) {
                    delete [] visited;
                    return true;
                }
            }
        }
        delete [] visited;
        return false;
    }
    bool hasPathCore(char* matrix, int rows, int cols,int row,int col, 
                     char* str,int& pathLength,bool* visited){
        if(str[pathLength] == '\0')
            return true;
        bool hasPath = false;
        if(row >= 0 && row < rows && col >=0 && col < cols
          && matrix[row * cols + col] == str[pathLength]  && !visited[row * cols + col]) {
            ++pathLength;
            visited[row * cols + col] = true;
            hasPath = hasPathCore(matrix,rows,cols,row+1,col,str,pathLength,visited)
                   || hasPathCore(matrix,rows,cols,row,col+1,str,pathLength,visited)
                   || hasPathCore(matrix,rows,cols,row-1,col,str,pathLength,visited)
                   || hasPathCore(matrix,rows,cols,row,col-1,str,pathLength,visited);
            if(!hasPath) {
                --pathLength;
                visited[row * cols + col] = false;
            }
        }
        return hasPath;
    }

// 机器人的运行范围
// 使用一个数组来记录已访问的位置，
//  从(0，0)出发， 每次移动位置都要检查是否满足要求。
// 如果满足要求则设置记录数组，并且增加路程

    int movingCount(int threshold, int rows, int cols)
    {
        if(threshold <= 0 || rows <= 0 || cols <= 0)
            return 0;
        bool *visited = new bool[rows * cols];
        for(int i = 0; i < rows * cols; ++i)
            visited[i] = false;
        int count = movingCountCore(threshold,rows,cols,0,0,visited);
        delete [] visited;
        return count;
    }
    int movingCountCore(int threshold, int rows, int cols,int row,int col,bool *visited){
        int pathLength = 0;
        if(row >=0 && row < rows && col >= 0 && col < cols 
           && !visited[row * cols + col] && checkOk(threshold, row, col)) {
            visited[row * cols + col] = true;
            pathLength = 1 + movingCountCore(threshold,rows,cols,row,col+1,visited)
                       + movingCountCore(threshold,rows,cols,row+1,col,visited)
                       + movingCountCore(threshold,rows,cols,row-1,col,visited)
                       + movingCountCore(threshold,rows,cols,row,col-1,visited);
         
        }
        return pathLength;
    }
    bool checkOk(int threshold, int row, int col)
    {
        int tmp = 0;
        while(row > 0){
            tmp += row % 10;
            row = row / 10;
        }
        while(col > 0){
            tmp += col % 10;
            col = col / 10;
        }
        if(tmp <= threshold)
            return true;
        return false;
    }

![@VSE[UFJXPMVHUAHS2{1PX.png

CH0DUHF}M)@4486{PU4(WCH.png

//从最左列开始，按照规定从上，下，右三个方向出发，把所有路径找到找到最小跳数
//设置一个数组用来记录路径标注已经过的格子放置重复，
// 判断当前位置是否正确，以及是否能到达右边