алгоритм нахождения числа 1 с в матрице (только вертикальные 1 с). Изображение говорит само за себя, что я хочу

Question

Алгоритм необходим для нахождения группы 1 в матрице, но группа 1 должна содержать только вертикальную запись

Answer 1

Это больше в категории головоломка.

Для маленьких матриц мы просто обращаемся к ним столбец за столбцом.

Предполагая, что input является двумерным массивом целых чисел, а output является списком следующего класса:

class GroupIdentifier {
  int col;
  int rowStart;
  int colStart; 

  /* the corresponding getter/setter/constructor etc */
}

Вот функция, которую вы ищете:

int FIRST_ONE = 2;
int IN_GROUP = 1;
int OUT_GROUP = 0;

public List<GroupIdentifier> findVerticalGroupsOf1 (int[][] a, 
  int numRow, int numCol) {
  List<GroupIdentifier> answer = new ArrayList<GroupIdentifier>();
  for (col = 0; col < numCol; col = col + 1) {
    // let's create the tempArr holding the current col
    int[] tempArr = new int[numRow];
    for (row = 0; row < numRow; row = row + 1 =) {
      tempArr[row] = a[row][col];
    }
    // let's find the groups
    // first, init the state
    int state = (tempArr[0] == 1) ? FIRST_ONE : OUT_GROUP;
    int start = (state == FIRST_ONE) ? 0 : -1;
    // I see this problem as a simple state-machine
    // We have three states: FIRST_ONE encountered (0 to 1),
    // still tracking the 1s IN_GROUP ... (1 to 1) and 
    // get OUT_GROUP (1 to 0). 
    // the switch case in the following loop does exactly that.
    // So, whenever we get an OUT_GROUP event, we get an answer.
    for (int i = 1; i < numRow; i = i + 1) { // edit: changed to numRow as
                                             // it was a typo error
      switch (state) : 
      case FIRST_ONE :
        if (tempArr[i] == 0)
          state = OUT_GROUP;
        else 
          state = IN_GROUP; 
        break;
      case IN_GROUP :
        if (tempArr[i] == 0) {
          GroupIdentifier gi = new GroupIdentifier (col, start, i - 1);
          answer.add(gi); 
        }
        break; 
      case OUT_GROUP :
        if (tempArr[i] == 1) {
          start = i; 
          state = FIRST_ONE;
        } 
        break; 
    }

  }
  // since this question looks like homework,
  // i will leave out the boundary case handling
  // here. it's not that hard; just copy/paste the
  // switch statement and fondle around.
  return answer; 
}

Как компьютерщик, я думаю о том, как его оптимизировать.

Для больших матриц я хотел бы предварительно вычислить все комбинации tempArr и сохранить их как Integer -> List map. Затем я перейду столбцы без вычислений снова.