专栏首页孟君的编程札记数独终盘生成的几种方法

数独终盘生成的几种方法

数独(すうどく,Sudoku)是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1-9,不重复。

一般情况下,产生一个数独题目,包含两个步骤:

  1. 产生一个数独终盘(9X9)
  2. 在第一步产生的数独终盘中,根据难易程度,在终盘上挖掉不同数目的数字。

经过该两个步骤之后,我们就可以将某一个数独难题展示出来,如:

本文列举数独终盘产生的几个方法,大家一起来看看吧。

矩阵转换法

矩阵转换法,简言之,就是对一个已有的数独终盘矩阵进行操作。 主要采用交换数字、交换行/列数据等方法,产生新的矩阵。

为了完成矩阵的转换,我们需要有可用的数独终盘矩阵作为种子矩阵才行。可以采用如下做法完成:

  • 先给定几个可用数独终盘作为备选种子矩阵。
  • 产生一个随机数,随机选中其中的一个作为种子矩阵。

如编写一个产生种子矩阵的工具类:

import java.util.Random;

/**
 * 
 * @author wangmengjun
 *
 */
public final class SeedSudokuMatrixFactory {

  private static final int seedSudokuArrays[][][] = {
      { { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, { 4, 5, 6, 7, 8, 9, 1, 2, 3 },
          { 7, 8, 9, 1, 2, 3, 4, 5, 6 },
          { 2, 1, 4, 3, 6, 5, 8, 9, 7 },
          { 3, 6, 5, 8, 9, 7, 2, 1, 4 },
          { 8, 9, 7, 2, 1, 4, 3, 6, 5 },
          { 5, 3, 1, 6, 4, 2, 9, 7, 8 },
          { 6, 4, 2, 9, 7, 8, 5, 3, 1 },
          { 9, 7, 8, 5, 3, 1, 6, 4, 2 } },
      { { 3, 9, 4, 5, 1, 7, 6, 2, 8 }, { 5, 1, 7, 6, 2, 8, 3, 9, 4 },
          { 6, 2, 8, 3, 9, 4, 5, 1, 7 },
          { 9, 3, 5, 4, 7, 1, 2, 8, 6 },
          { 4, 7, 1, 2, 8, 6, 9, 3, 5 },
          { 2, 8, 6, 9, 3, 5, 4, 7, 1 },
          { 1, 4, 3, 7, 5, 9, 8, 6, 2 },
          { 7, 5, 9, 8, 6, 2, 1, 4, 3 },
          { 8, 6, 2, 1, 4, 3, 7, 5, 9 } },
      { { 7, 6, 1, 9, 8, 4, 2, 3, 5 }, { 9, 8, 4, 2, 3, 5, 7, 6, 1 },
          { 2, 3, 5, 7, 6, 1, 9, 8, 4 },
          { 6, 7, 9, 1, 4, 8, 3, 5, 2 },
          { 1, 4, 8, 3, 5, 2, 6, 7, 9 },
          { 3, 5, 2, 6, 7, 9, 1, 4, 8 },
          { 8, 1, 7, 4, 9, 6, 5, 2, 3 },
          { 4, 9, 6, 5, 2, 3, 8, 1, 7 },
          { 5, 2, 3, 8, 1, 7, 4, 9, 6 } },
      { { 7, 1, 5, 4, 3, 6, 2, 9, 8 }, { 4, 3, 6, 2, 9, 8, 7, 1, 5 },
          { 2, 9, 8, 7, 1, 5, 4, 3, 6 },
          { 1, 7, 4, 5, 6, 3, 9, 8, 2 },
          { 5, 6, 3, 9, 8, 2, 1, 7, 4 },
          { 9, 8, 2, 1, 7, 4, 5, 6, 3 },
          { 3, 5, 7, 6, 4, 1, 8, 2, 9 },
          { 6, 4, 1, 8, 2, 9, 3, 5, 7 },
          { 8, 2, 9, 3, 5, 7, 6, 4, 1 } } };

  private SeedSudokuMatrixFactory() {
  }

  /**
   * 随机获取一个预先定义好的数独数组
   */
  public static int[][] retrieveSeedSudokuArrayByRandom() {
    int randomInt = new Random().nextInt(seedSudokuArrays.length);
    return seedSudokuArrays[randomInt].clone();
  }
}
}

有了种子矩阵之后,我们就可以对某个种子矩阵做矩阵转换处理,从而获取更多的可用的数独终盘矩阵。

两个数互相交换法

下图就是一个数字9和数据1交换的例子:

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 
 * @author wangmengjun
 *
 */
public class SudokuPuzzleMatrixGenerator {

  /** 待转换的数组种子数组 */
  private int[][] sampleArray = SeedSudokuMatrixFactory
      .retrieveSeedSudokuArrayByRandom();

  public int[][] generateSudokuArray() {
    List<Integer> randomList = buildRandomList();
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        for (int k = 0; k < 9; k++) {
          if (sampleArray[i][j] == randomList.get(k)) {
            sampleArray[i][j] = randomList.get((k + 1) % 9);
            break;
          }
        }
      }
    }
    return sampleArray;
  }

  private List<Integer> buildRandomList() {
    List<Integer> result = Arrays.asList( 1, 2, 3, 4, 5, 6, 7, 8, 9 );
    Collections.shuffle(result);
    return result;
  }

}
/**
 * 
 * @author wangmengjun
 *
 */
public class Main {

  public static void main(String[] args) {
    int[][] grids = new SudokuPuzzleMatrixGenerator().generateSudokuArray();
    printArray(grids);
  }
  
  /**
   * 打印二维数组到控制台
   */
  private static void printArray(int[][] grids) {
    for (int i = 0; i < 9; i++) {
      if (i % 3 == 0) {
        System.out.println(" -----------------------");
      }
      for (int j = 0; j < 9; j++) {
        if (j % 3 == 0) {
          System.out.print("| ");
        }
        System.out.print(grids[i][j] == 0 ? " " : grids[i][j]);
        System.out.print(" ");
      }
      System.out.println("|");
    }
    System.out.println(" -----------------------");
  }

}

某次运行的结果:

 -----------------------
| 3 5 4 | 2 7 9 | 6 1 8 |
| 2 7 9 | 6 1 8 | 3 5 4 |
| 6 1 8 | 3 5 4 | 2 7 9 |
 -----------------------
| 5 3 2 | 4 9 7 | 1 8 6 |
| 4 9 7 | 1 8 6 | 5 3 2 |
| 1 8 6 | 5 3 2 | 4 9 7 |
 -----------------------
| 7 4 3 | 9 2 5 | 8 6 1 |
| 9 2 5 | 8 6 1 | 7 4 3 |
| 8 6 1 | 7 4 3 | 9 2 5 |
 -----------------------

调整行或者列

下面就是两列互换的例子。对于行或者列,需要保证:

交换只发生在前三行,中间三行,最后三行,前三列,中间三列以及最后三列之间。 而不能越界交换,比如第一行和第四行交换就是不允许的。

交换行

  public int[][] generateSudokuArray1() {  
    Random random = new Random();
        int randomRowNum = 0;  
        //随机交换20次  
        for (int i = 0; i < 20; i++) {  
            randomRowNum = random.nextInt(8) + 1;  
            for (int col = 0; col < 9; col++) {  
                if(randomRowNum % 3 ==0)  
                {  
                    int temp = sampleArray[randomRowNum][col];  
                    sampleArray[randomRowNum][col] = sampleArray[randomRowNum+1][col];  
                    sampleArray[randomRowNum+1][col] = temp;  
                }  
                else  
                {  
                    int temp = sampleArray[randomRowNum][col];  
                    sampleArray[randomRowNum][col] = sampleArray[randomRowNum-1][col];  
                    sampleArray[randomRowNum-1][col] = temp;  
                }  
  
            }  
  
        }  
        return sampleArray;  
    }

交换列

public int[][] generateSudokuArray2() {  
      Random random = new Random();
        int randomColumnNum = 0;  
        for (int i = 0; i < 20; i++) {  
            randomColumnNum = random.nextInt(8) + 1;  
            for (int row = 0; row < 9; row++) {  
                  
                if(randomColumnNum %3 ==0)  
                {  
                    int temp = sampleArray[row][randomColumnNum];  
                    sampleArray[row][randomColumnNum] = sampleArray[row][randomColumnNum+1];  
                    sampleArray[row][randomColumnNum+1] = temp;  
                }else  
                {  
                    int temp = sampleArray[row][randomColumnNum];  
                    sampleArray[row][randomColumnNum] = sampleArray[row][randomColumnNum-1];  
                    sampleArray[row][randomColumnNum-1] = temp;  
                }  
                  
            }  
        }  
        return sampleArray;  
    }

交换行的一个测试示例:

/**
 * 
 * @author wangmengjun
 *
 */
public class Main {

  public static void main(String[] args) {
    int[][] grids = new SudokuPuzzleMatrixGenerator().generateSudokuArray1();
    printArray(grids);
  }
  
  /**
   * 打印二维数组到控制台
   */
  private static void printArray(int[][] grids) {
    for (int i = 0; i < 9; i++) {
      if (i % 3 == 0) {
        System.out.println(" -----------------------");
      }
      for (int j = 0; j < 9; j++) {
        if (j % 3 == 0) {
          System.out.print("| ");
        }
        System.out.print(grids[i][j] == 0 ? " " : grids[i][j]);
        System.out.print(" ");
      }
      System.out.println("|");
    }
    System.out.println(" -----------------------");
  }

}

某次运行的结果:

 -----------------------
| 2 3 5 | 7 6 1 | 9 8 4 |
| 7 6 1 | 9 8 4 | 2 3 5 |
| 9 8 4 | 2 3 5 | 7 6 1 |
 -----------------------
| 3 5 2 | 6 7 9 | 1 4 8 |
| 6 7 9 | 1 4 8 | 3 5 2 |
| 1 4 8 | 3 5 2 | 6 7 9 |
 -----------------------
| 4 9 6 | 5 2 3 | 8 1 7 |
| 5 2 3 | 8 1 7 | 4 9 6 |
| 8 1 7 | 4 9 6 | 5 2 3 |
 -----------------------

调整块的位置

矩阵旋转

另外,还可以以对角线对对称,交换数据等方式,如:

public int[][] getArrayWithDiagonalSymmetry() {  
    int[][] result = new int[9][9];  
    for (int i = 0; i < 9; i++) {  
        for (int j = 0; j < 9; j++) {   
            result[i][j] = sampleArray[j][i];  
        }  
    }  
    return result;  
}

随机法

矩阵转换法生成数独终盘的方式具有方便速度块的特点。 它的缺点产生的终盘的随机性不是很强,毕竟是从一个固定的种子矩阵转换而得的。

之前的一篇博文,讲解过回溯法解数独,如果初始为空的二维数组,在遍历的时候,可以将1-9的候选数随机化,这样就能产生相对随机性较大的数独了。因为已经在之前博客讲过,这里就不再叙述。

本文给出一个随机产生数独终盘的另外一种方法。

该种方法就是考虑到,数独的数量很多。 (约有6.67×10的21次方)种组合

终盘数量

终盘数量数独中的数字排列千变万化,那么究竟有多少种终盘的数字组合呢? 6,670,903,752,021,072,936,960(约有6.67×10的21次方)种组合,2005年由Bertram Felgenhauer和Frazer Jarvis计算出该数字,并将计算方法发布在他们网站上,如果将等价终盘(如旋转、翻转、行行对换,数字对换等变形)不计算,则有5,472,730,538个组合。数独终盘的组合数量都如此惊人,那么数独题目数量就更加不计其数了,因为每个数独终盘又可以制作出无数道合格的数独题目。

参考自http://baike.baidu.com/link?url=ePXUCvpBaRKBkEA3pVfOkg3m-NBozO6a4GDS0N3E5_gK1nnJCDzd5O-YL1w7c5S3

假设

按照这个数量,如果我们将一个[1,2,3,4,5,6,7,8,9]的数组随机化,然后将其作为一行数据添加到一个二维数组中去,该行能满足数独终盘规则的概率是很大的。

思想

基于这个假设(假设的有效性会在文章后面验证),随机算法思想如下:

  • 写一个方法用于获取一个由1到9九个数随机排列的一维数组。
  • 循环行(下标从0到8),将这个随机产生的一维数组作为当前行的内容,如果是第一行(行标为0),那么直接作为该行的内容。如果是其它行,则验证数据是否都符合条件。
  • 如果符合条件,则再产生一个由1到9九个数随机排列的一维数组作为下一行的内容并验证数据是否可用。如果不符合条件,则将该行数据设置为0,调整row和col,产生一个由1到9九个数随机排列的一维数组,重新对该行验证。
  • 程序中为了防止产生一维随机数组的方法调用很多次而没有产生结果,设置一个最多调用该方法次数的阈值,当达到这个阈值还没有产生结果,重新从 row =0 col =0 开始。
import java.util.Random;  
/**
 * 
 * @author wangmengjun
 *
 */ 
public class SudokuPuzzleGenerator {  
  
    private Random random = new Random();  
      
    /**运行此程序300次,最大值是217,最小值11,平均约等于50 
     * 阈值设置为220, 能满足大部分程序,二维矩阵不会置为0,重新再产生值。
     */  
    private static final int MAX_CALL_RANDOM_ARRAY_TIMES = 220;  
  
    /**记录当前buildRandomArray()方法调用的次数*/  
    private int currentTimes = 0;  
  
    public int[][] generatePuzzleMatrix() {  
  
        int[][] randomMatrix = new int[9][9];  
  
        for (int row = 0; row < 9; row++) {  
            if (row == 0) {  
                currentTimes = 0;  
                randomMatrix[row] = buildRandomArray();  
  
            } else {  
                int[] tempRandomArray = buildRandomArray();  
  
                for (int col = 0; col < 9; col++) {  
                    if (currentTimes < MAX_CALL_RANDOM_ARRAY_TIMES) {  
                        if (!isCandidateNmbFound(randomMatrix, tempRandomArray,  
                                row, col)) {  
                              
                            /* 
                             * 将该行的数据置为0,并重新为其准备一维随机数数组 
                             */  
                            resetValuesInRowToZero(randomMatrix,row);  
                            row -= 1;  
                            col = 8;  
                            tempRandomArray = buildRandomArray();  
                        }  
                    } else {  
                        /** 
                         * 将二维矩阵中的数值置为0, 
                         * row赋值为-1 col赋值为8, 下一个执行的就是row =0 col=0, 
                         *  
                         * 重头开始 
                         */  
                        row = -1;  
                        col = 8;  
                        resetValuesToZeros(randomMatrix);  
                        currentTimes = 0;  
                    }  
                }  
            }  
        }  
        return randomMatrix;  
    }  
      
    private void resetValuesInRowToZero(int[][] matrix, int row)  
{  
        for (int j = 0; j < 9; j++) {  
            matrix[row][j] = 0;  
        }  
          
    }  
  
    private void resetValuesToZeros(int[][] matrix) {  
        for (int row = 0; row < 9; row++) {  
            for (int col = 0; col < 9; col++) {  
                matrix[row][col] = 0;  
            }  
        }  
    }  
  
    private boolean isCandidateNmbFound(int[][] randomMatrix,  
            int[] randomArray, int row, int col) {  
        for (int i = 0; i < randomArray.length; i++) {  
            /** 
             * 试着给randomMatrix[row][col] 赋值,并判断是否合理 
             */  
            randomMatrix[row][col] = randomArray[i];  
            if (noConflict(randomMatrix, row, col)) {  
                return true;  
            }  
        }  
        return false;  
    }  
  
    private boolean noConflict(int[][] candidateMatrix, int row, int col) {  
        return noConflictInRow(candidateMatrix, row, col)  
                && noConflictInColumn(candidateMatrix, row, col)  
                && noConflictInBlock(candidateMatrix, row, col);  
    }  
  
    private boolean noConflictInRow(int[][] candidateMatrix, int row, int col) {  
        /** 
         * 因为产生随机数矩阵是按照先行后列,从左到右产生的 ,该行当前列后面的所有列的值都还是0, 所以在行比较的时候, 
         * 只要判断该行当前列与之前的列有无相同的数字即可。
         *  
         */  
        int currentValue = candidateMatrix[row][col];  
  
        for (int colNum = 0; colNum < col; colNum++) {  
            if (currentValue == candidateMatrix[row][colNum]) {  
                return false;  
            }  
        }  
  
        return true;  
    }  
  
    private boolean noConflictInColumn(int[][] candidateMatrix, int row, int col) {  
  
        /** 
         * 与noConflictInRow(...)方法类似:
         *  
         *  
         * 因为产生随机数矩阵是按照先行后列,从左到右产生的,该列当前行后面的所有行的值都还是0, 
         *  
         * 所以在列比较的时候, 只要判断该列当前行与之前的行有无相同的数字即可。
         *  
         */  
  
        int currentValue = candidateMatrix[row][col];  
  
        for (int rowNum = 0; rowNum < row; rowNum++) {  
            if (currentValue == candidateMatrix[rowNum][col]) {  
                return false;  
            }  
        }  
  
        return true;  
    }  
  
    private boolean noConflictInBlock(int[][] candidateMatrix, int row, int col) {  
  
        /** 
         * 为了比较3 x 3 块里面的数是否合理, 需要确定是哪一个Block,我们先要求出3 x 3的起始点。比如:Block 1 
         * 的起始点是[0][0] Block 2 的起始点是[3]][0] 
         *  
         * ... Block 9 的起始点是[6][6] 
         */  
  
        int baseRow = row / 3 * 3;  
        int baseCol = col / 3 * 3;  
  
        for (int rowNum = 0; rowNum < 8; rowNum++) {  
            if (candidateMatrix[baseRow + rowNum / 3][baseCol + rowNum % 3] == 0) {  
                continue;  
            }  
            for (int colNum = rowNum + 1; colNum < 9; colNum++) {  
                if (candidateMatrix[baseRow + rowNum / 3][baseCol + rowNum % 3] == candidateMatrix[baseRow  
                        + colNum / 3][baseCol + colNum % 3]) {  
                    return false;  
                }  
            }  
        }  
        return true;  
  
    }  
  
    /** 
     * 返回一个有1到9九个数随机排列的一维数组, 
     */  
    private int[] buildRandomArray() {  
        currentTimes++;  
        int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };  
        int randomInt = 0;  
        /** 
         * 随机产生一个1到8的随机数,使得该下标的数值与下标为0的数值交换, 
         *  
         *  处理20次,能够获取一个有1到9九个数随机排列的一维数组, 
         */  
        for (int i = 0; i < 20; i++) {  
            randomInt = random.nextInt(8) + 1;  
            int temp = array[0];  
            array[0] = array[randomInt];  
            array[randomInt] = temp;  
        }  
  
        return array;  
    }  
  
    /** 
     * @return the currentTimes 
     */  
    public int getCurrentTimes() {  
        return currentTimes;  
    }  
  
    /** 
     * @param currentTimes the currentTimes to set 
     */  
    public void setCurrentTimes(int currentTimes) {  
        this.currentTimes = currentTimes;  
    }  
      
}
/**
 * 
 * @author wangmengjun
 *
 */
public class Main {

  public static void main(String[] args) {
    SudokuPuzzleGenerator example = new SudokuPuzzleGenerator();
    for(int i=1;i<=3;i++) {
      int[][] grids = example.generatePuzzleMatrix();
      printArray(grids);
      System.out.println();
    }
  }

  /**
   * 打印二维数组到控制台
   */
  private static void printArray(int[][] grids) {
    for (int i = 0; i < 9; i++) {
      if (i % 3 == 0) {
        System.out.println(" -----------------------");
      }
      for (int j = 0; j < 9; j++) {
        if (j % 3 == 0) {
          System.out.print("| ");
        }
        System.out.print(grids[i][j] == 0 ? " " : grids[i][j]);
        System.out.print(" ");
      }
      System.out.println("|");
    }
    System.out.println(" -----------------------");
  }

}

某次测试的结果:

 -----------------------
| 6 2 1 | 3 5 9 | 7 8 4 |
| 4 5 7 | 6 2 8 | 3 1 9 |
| 8 3 9 | 7 4 1 | 2 5 6 |
 -----------------------
| 1 4 2 | 5 3 6 | 9 7 8 |
| 3 6 8 | 4 9 7 | 5 2 1 |
| 7 9 5 | 8 1 2 | 4 6 3 |
 -----------------------
| 9 8 6 | 2 7 4 | 1 3 5 |
| 2 1 3 | 9 6 5 | 8 4 7 |
| 5 7 4 | 1 8 3 | 6 9 2 |
 -----------------------

 -----------------------
| 2 5 1 | 8 6 3 | 7 9 4 |
| 7 3 9 | 2 4 5 | 6 1 8 |
| 6 8 4 | 7 9 1 | 2 3 5 |
 -----------------------
| 1 2 5 | 4 8 7 | 3 6 9 |
| 4 6 3 | 5 2 9 | 1 8 7 |
| 8 9 7 | 1 3 6 | 5 4 2 |
 -----------------------
| 9 1 2 | 6 5 4 | 8 7 3 |
| 3 7 8 | 9 1 2 | 4 5 6 |
| 5 4 6 | 3 7 8 | 9 2 1 |
 -----------------------

 -----------------------
| 4 3 2 | 8 7 9 | 6 1 5 |
| 6 8 7 | 2 1 5 | 4 3 9 |
| 1 5 9 | 3 4 6 | 7 2 8 |
 -----------------------
| 5 9 1 | 4 8 7 | 2 6 3 |
| 3 6 8 | 1 9 2 | 5 7 4 |
| 7 2 4 | 6 5 3 | 8 9 1 |
 -----------------------
| 8 4 3 | 7 6 1 | 9 5 2 |
| 2 7 5 | 9 3 8 | 1 4 6 |
| 9 1 6 | 5 2 4 | 3 8 7 |
 -----------------------

假设有效性验证及阈值设定 针对上述的代码,我跑10组,每组30个实例,看看这300个例子中,产生数独终盘所需要调用随机产生由1到9的一维数组的次数各是多少, 结果如下:

从上面的结果图中可以看出:

300个实例中,调用次数最小的为11,接近理想最小调用次数9. 最大值为217次,平均约50次。而且大部分实例调用的次数在100以内。

从这些数据分析中,上述假设基本上是合适的,阈值最后选择了接近实验最大值217的220(如果尝试次数大于220还没有完成,则重新尝试)。

小结

本文给出了数独终盘产生的几种方法,主要有矩阵转换发以及随机法。

大家如有什么其它方法,也请告知一下:)

本文分享自微信公众号 - 孟君的编程札记(gh_0f0f5e0ae1de),作者:孟君

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [动态规划] 数字三角形问题(一维数组实现)

    一个数字三角宝塔。设数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层,每一步可沿左斜线向下或右斜线向下走。假设三角形行数小于等于100编程求解...

    孟君
  • 24点解法

    24点游戏是小时候很喜欢玩的游戏,给出4个数,通过加、减、乘、除完成运算,最终得到结果为24。比如数字1、3、5和9,可以通过3 * 5 + 9 * 1 得到结...

    孟君
  • 可视化排序实践之冒泡排序

    这样,一个简单地,模拟执行结合排序变化的例子就完成了。:) 有兴趣的读者可以试一试。

    孟君
  • LeetCode 135 Candy

    ShenduCC
  • LeetCode 75. Sort Colors题目分析

    给定一个包含红,白,蓝且长度为 n 的数组,将数组元素进行分类使相同颜色的元素相邻,并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0,1 和 2 分别代...

    desperate633
  • 1009 产生数 2002年NOIP全国联赛普及组

    009 产生数 2002年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 De...

    attack
  • POJ-3866-Exclusive Access 2

    ACM模版 描述 ? ? ? 题解 这绝对是我做过最长的题,也是最难理解的题,翻译成中文都很难理解。 简单的说,就是安排任务使用两个资源的顺序,使最坏情况下,执...

    f_zyj
  • HDU 3078 Network

    Problem Description The ALPC company is now working on his own network system,...

    attack
  • 最大子段和问题

    问题描述: 给定长度为n的整数序列,a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大,或者求出最大的这个和。如果该序列的...

    我没有三颗心脏
  • POJ-1088 滑雪 (记忆化搜索,dp)

    滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券