如何使用递归在2D数组中标记组? [英] How to label groups within a 2D array using recursion?

问题描述

我需要在我的代码中编写一个方法，该方法可以采用二维数组，并返回数组中有多少个不同的组.一组定义为"在上/下/左/右(非对角线)方向上直接连接到其他单元的所有单元" ，其中阵列中的单元将用星号表示.我需要编写一个遍历整个数组的方法，该方法还调用一个递归方法，该方法将每个星号更改为该组唯一的字母.例如，这是一个示例输入:

I need to write a a method in my code that can take a two dimensional array and return how many different groups there are within the array. A group is defined as, "all cells connected directly to other cells in the up/down/left/right (not diagonal) directions" where a cell in the array would be represented by an asterisk. I need to write a method that iterates through the entire array that also calls a recursive method that changes every asterisk into a letter that is unique to that group. For example this is a sample input:

char image[][] = {
        {'*','*',' ',' ',' ',' ',' ',' ','*',' '},
        {' ','*',' ',' ',' ',' ',' ',' ','*',' '},
        {' ',' ',' ',' ',' ',' ','*','*',' ',' '},
        {' ','*',' ',' ','*','*','*',' ',' ',' '},
        {' ','*','*',' ','*',' ','*',' ','*',' '},
        {' ','*','*',' ','*','*','*','*','*','*'},
        {' ',' ',' ',' ',' ',' ',' ',' ','*',' '},
        {' ',' ',' ',' ',' ',' ',' ',' ','*',' '},
        {' ',' ',' ','*','*','*',' ',' ','*',' '},
        {' ',' ',' ',' ',' ','*',' ',' ','*',' '}};

，输出将是这样的:

    aa      b 
     a      b 
          cc  
     d  ccc   
     dd c c c 
     dd cccccc
            c 
            c 
       eee  c 
         e  c 

我主要需要遍历给定图像的方法的帮助，因为我不知道如何使代码区分组.

I mostly need help with the method that iterates through the given image because I don't know how to make the code distinguish between the groups.

推荐答案

您的概念应该是这样的.

Your concept should be like this.

checkField (x, y, char)
  x,y is out of bounds; return;

  if current field has asterix do
     current field = char; // Prevents new checks!
     checkField (x+1, y, char); // right field
     checkField (x+-1,y, char); //l left field 
     // top and bottem field.
  else do
    // Advance to next Field; Next field has to be in bounds. At the end of the line you have to go to the next line;
    checkField( .., ..., char++)
end;

第一个调用将是 checkField(0，0，'a');

您需要创建一个新的字符数组.这将是一个实例变量.

You need to create a new array of chars. This would be an instance variable.

您可以将x，y矩阵建模为数组.其中x mod y是一条线.这将使进步更加容易.但是直觉更少.

You could model the x, y matrix as array. Where x mod y is a line. This would make advanceing easier. But less intuitiv.

尝试实现伪代码，并随时详细更新您的问题.

Try to implement the pseudocode and feel free to update you question in detail.

这篇关于如何使用递归在2D数组中标记组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！