java - 如何在二维矩阵中找到相同元素的行？

Question

我有自定义大小的矩阵，应该找到具有指定长度的行。我需要该行中第一个和最后一个元素的坐标。
例如:
线长为3。
我的矩阵是

• 0 0 0 1 0 0 1
• 0 0 0 1 0 0 0
• 0 0 0 1 0 0 0
• 1 0 1 0 0 0 0

所以我的答案是 [0, 3], [2, 3]。

如果行长为4。
我的矩阵是

• 0 0 0 0 1 0 0
• 0 0 0 1 0 0 0
• 1 0 1 0 0 0 0
• 0 1 0 0 0 0 0

我的答案是 [0, 4], [3, 1]。

元素可以具有任何类型(数字、字符、字符串、对象等)。
使用什么编程语言并不重要，因为我只想了解算法。
对不起，我的英语不好。感谢您的帮助。

Answer 1

这不是您问题的确切解决方案，但它应该足够接近，以便您能够转移它:

#include <stdio.h>
#include <stdbool.h>

#define WIDTH   8
#define HEIGHT  8

bool matrix[HEIGHT][WIDTH] =
{
    { 0, 0, 0, 1, 0, 0, 0, 1 },
    { 1, 0, 1, 0, 1, 0, 1, 1 },
    { 1, 1, 1, 0, 0, 1, 1, 1 },
    { 1, 1, 1, 1, 1, 0, 0, 0 },
    { 0, 1, 0, 0, 0, 0, 0, 0 },
    { 1, 0, 1, 1, 0, 0, 0, 0 },
    { 1, 1, 1, 1, 0, 0, 0, 0 },
    { 1, 1, 1, 1, 0, 0, 0, 0 },
};

struct position
{
    int row;
    int column;
};

enum direction { south, east, southwest, southeast };
char *dir_s[] = { "south", "east", "southwest", "southeast" };


int search(bool m[WIDTH][HEIGHT], struct position start, enum direction dir)
{
    switch (dir)
    {
        case east:
            if ((++start.column < WIDTH) && m[start.row][start.column])
            {
                return 1 + search(m, start, east);
            }
            break;

        case south:
            if ((++start.row < HEIGHT) && m[start.row][start.column])
            {
                return 1 + search(m, start, south);
            }
            break;

        case southwest:    
            if ((++start.row < HEIGHT) && (--start.column >= 0) && m[start.row][start.column])
            {
                return 1 + search(m, start, southwest);
            }
            break;

        case southeast:
            if ((++start.row < HEIGHT) && (++start.column < WIDTH) && m[start.row][start.column])
            {
                return 1 + search(m, start, southeast);
            }
    }
    return 0;
}


int main(int argc, char *argv[])
{
    struct position maxpos;
    enum direction maxdir;
    int length;
    int maxlength = 0;

    for (int column = 0; column < WIDTH; column++)
        for (int row = 0; row < HEIGHT; row++)
            if (matrix[row][column])
            {
                struct position pos = { row, column };
                enum direction dir;

                for (dir = south; dir <= southeast; dir++)
                {
                    length =  1 + search(matrix, pos, dir);
                    if (length > maxlength)
                    {
                        maxlength = length;
                        maxdir = dir;
                        maxpos = pos;
                    }
                }
            }
    printf("found max length %d on (%d,%d) in direction %s\n", maxlength, maxpos.row, maxpos.column, dir_s[maxdir]);
}

请注意，搜索会递归调用自身，因此最好不要将其用于非常大的数据集。