Форум программистов, компьютерный форум CyberForum.ru

Найти наиболее длинную цепочку в двумерном массиве - C++

Восстановить пароль Регистрация
 
p.pavluxa
1 / 1 / 0
Регистрация: 30.07.2011
Сообщений: 15
29.06.2012, 17:31     Найти наиболее длинную цепочку в двумерном массиве #1
Здравствуйте. Помогите пожалуйста решить одну задачку на любом языке программировании (желательно PHP): в целочисленном двумерном массиве найти наиболее длинную цепочку одинаковых подряд стоящих элементов (кроме нуля) по вертикали либо горизонтали либо по диагонали (основной и побочной). Вернуть длину этой цепочки и элемент её составляющей.

Пожалуйста, уже всю голову сломал.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.06.2012, 17:31     Найти наиболее длинную цепочку в двумерном массиве
Посмотрите здесь:

В последовательности найти наиболее длинную последовательность подряд идущих нулей C++
В целочисленном массиве найти наиболее длинную цепочку одинаковых подряд стоящих элементов C++
Найти самую длинную возрастающую цепочку простых чисел C++
найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц C++
C++ Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
29.06.2012, 20:53     Найти наиболее длинную цепочку в двумерном массиве #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <stdio.h>
#include <conio.h>
#include <memory.h>
 
#define N 10
 
int main()
{
    int X[N][N] = { { 2, 5, 1, 5, 8, 1, 6, 2, 2, 3 },
                    { 9, 4, 7, 6, 5, 8, 5, 3, 8, 9 },
                    { 8, 3, 4, 5, 5, 5, 5, 8, 7, 7 },
                    { 1, 2, 4, 4, 5, 6, 2, 7, 4, 6 },
                    { 7, 1, 5, 5, 4, 4, 1, 6, 6, 2 },
                    { 6, 6, 6, 4, 1, 4, 4, 1, 3, 5 },
                    { 3, 7, 9, 7, 6, 5, 9, 4, 2, 4 },
                    { 4, 8, 1, 9, 2, 8, 5, 5, 5, 2 },
                    { 5, 9, 4, 6, 3, 2, 8, 3, 2, 3 },
                    { 7, 1, 3, 3, 5, 7, 3, 3, 1, 1 } };
 
    int max_i = 0;
    int max = 0, r = 0;
    int **Y = new int*[2 * N];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int k = j;
            while (X[i][j] == X[i][j+1]) j++;
            if (j-k+1 > 1)
            {
                Y[r] = new int[2 * N];
                memset((void*)Y[r], 0x00, sizeof(int) * 2 * N);
                for (int d = k, x = 0; d <= j; d++)
                    Y[r][x++] = X[i][d];
 
                if (j-k+1 > max) { max = j-k+1; max_i = r; }
 
                r++;
            }
        }
    }
 
    printf("HORIZONTAL:\n");
 
    for (int z = 0; z < r; z++)
    {
        printf("%d - ",z);
        for (int t = 0; Y[z][t] != 0; t++)
            printf("%d ",Y[z][t]);
        printf("\n");
    }
 
    printf("---------------------------------\n");
    for (int z1 = 0; Y[max_i][z1] != 0; z1++)
        printf("%d ",Y[max_i][z1]);
 
    int max_j = 0;
    max = 0; r = 0; Y = new int*[2 * N];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int k = j;
            while (X[j][i] == X[j+1][i]) j++;
            if (j-k+1 > 1)
            {
                Y[r] = new int[2 * N];
                memset((void*)Y[r], 0x00, sizeof(int) * 2 * N);
                for (int d = k, x = 0; d <= j; d++)
                    Y[r][x++] = X[d][i];
 
                if (j-k+1 > max) { max = j-k+1; max_j = r; }
 
                r++;
            }
        }
    }   
 
    printf("\n\nVERTICAL:\n");
 
    for (int z2 = 0; z2 < r; z2++)
    {
        printf("%d - ",z2);
        for (int t = 0; Y[z2][t] != 0; t++)
            printf("%d ",Y[z2][t]);
        printf("\n");
    }
 
    printf("---------------------------------\n");
    for (int z3 = 0; Y[max_j][z3] != 0; z3++)
        printf("%d ",Y[max_j][z3]);
 
    int* A = new int[N]; int x = 0;
    for (int j1 = 0; j1 < N; j1++)
        A[x++] = X[j1][j1];
 
    int* B = new int[N]; int y = 0;
    for (int j2 = 0; j2 < N; j2++)
        B[y++] = X[j2][N-j2-1];
 
    Y = new int*[2 * N];
    max_j = 0; max = 0; r = 0; 
    for (int w = 0; w < N; w++)
    {
        int m = w;
        while (A[w] == A[w+1]) w++;
        if (w-m+1 > 1)
        {
            Y[r] = new int[2 * N];
            memset((void*)Y[r], 0x00, sizeof(int) * 2 * N);
            for (int d = m, x = 0; d <= w; d++)
                Y[r][x++] = A[d];
 
            if (w-m+1 > max) { max = w-m+1; max_j = r; }
 
            r++;
        }
    }
 
    printf("\n\nDIAGONAL:\n");
 
    for (int z4 = 0; z4 < r; z4++)
    {
        printf("%d - ",z4);
        for (int t = 0; Y[z4][t] != 0; t++)
            printf("%d ",Y[z4][t]);
        printf("\n");
    }
 
    printf("---------------------------------\n");
    for (int z5 = 0; Y[max_j][z5] != 0; z5++)
        printf("%d ",Y[max_j][z5]);
 
    Y = new int*[2 * N];
    max_j = 0; max = 0; r = 0; 
    for (int v = 0; v < N; v++)
    {
        int m = v;
        while (B[v] == B[v+1]) v++;
        if (v-m+1 > 1)
        {
            Y[r] = new int[2 * N];
            memset((void*)Y[r], 0x00, sizeof(int) * 2 * N);
            for (int d = m, x = 0; d <= v; d++)
                Y[r][x++] = B[d];
 
            if (v-m+1 > max) { max = v-m+1; max_j = r; }
 
            r++;
        }
    }
 
    printf("\n\nREVERSE DIAGONAL:\n");
 
    for (int z6 = 0; z6 < r; z6++)
    {
        printf("%d - ",z6);
        for (int t = 0; Y[z6][t] != 0; t++)
            printf("%d ",Y[z6][t]);
        printf("\n");
    }
 
    printf("---------------------------------\n");
    for (int z7 = 0; Y[max_j][z7] != 0; z7++)
        printf("%d ",Y[max_j][z7]);
 
    _getch();
 
    return 0;
}
http://liveworkspace.org/code/5648e9...75806e098bd5c8
p.pavluxa
1 / 1 / 0
Регистрация: 30.07.2011
Сообщений: 15
29.06.2012, 20:58  [ТС]     Найти наиболее длинную цепочку в двумерном массиве #3
Супер! Спасибо! Вы гений!

Добавлено через 43 секунды
А если матрица будет не квадратная?
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
29.06.2012, 20:59     Найти наиболее длинную цепочку в двумерном массиве #4
То, возможен поиск только по вертикали и горизонтали.
p.pavluxa
1 / 1 / 0
Регистрация: 30.07.2011
Сообщений: 15
29.06.2012, 21:01  [ТС]     Найти наиболее длинную цепочку в двумерном массиве #5
Вот это плохо ( Нужно что бы в прямоугольниках по диагоналям искало ((
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
29.06.2012, 21:02     Найти наиболее длинную цепочку в двумерном массиве #6
Ладно посмотрим что можно сделать.
p.pavluxa
1 / 1 / 0
Регистрация: 30.07.2011
Сообщений: 15
29.06.2012, 21:04  [ТС]     Найти наиболее длинную цепочку в двумерном массиве #7
Я мог без проблем добиться того что по вертикали и горизонтали, а вот с диагоналями полная запара ((

Мне это нужно для игры в крестики нолики на динамическом поле.
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
29.06.2012, 21:07     Найти наиболее длинную цепочку в двумерном массиве #8
Точнее сейчас немогу, занят.

Добавлено через 2 минуты
Если кол-во строк или столбцов прямоугольн. матрицы нечетные, то разбить ее на квадраты будет сложно, поскольку будут отдельные строки или столбцы которые оставшиеся при делении. Вообще-то, это большой проект.
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
29.06.2012, 21:10     Найти наиболее длинную цепочку в двумерном массиве #9
А что такого сложного при движении по диагонали? При движении по диагонали, параллельной главной, для каждого следующего элемента мы увеличиваем на 1 и номер строки, и номер столбца. Так что тут возникает только 2 вопроса: какие элементы выбирать в качестве начальных и когда останавливаться. Ответ тоже вполне очевиден - начинать надо с элементов первого столбца и первой строки, а останавливаться - когда упрёмся либо в последний столбец, либо в последнюю строку.

Аналогично и с побочными диагоналями, только там мы уже номер строки увеличиваем, а номер столбца уменьшаем. Начинать надо уже с элементов последнего столбца и первой строки, а заканчивать, когда упираемся в последнюю строку или первый столбец.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.06.2012, 21:16     Найти наиболее длинную цепочку в двумерном массиве
Еще ссылки по теме:

Цикл: Найти самую длинную неубывающую цепочку чисел C++
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц C++
Найти в матрице самую длинную цепочку подряд стоящих 0 по горизонтали или вертикали C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
p.pavluxa
1 / 1 / 0
Регистрация: 30.07.2011
Сообщений: 15
29.06.2012, 21:16  [ТС]     Найти наиболее длинную цепочку в двумерном массиве #10
Ну а если взять задачку чуть полегче. У меня есть прямоугольная доска состоящая из 0 1 и 2, мне нужно проверить есть ли в ней одинаковые подрядидущие 1 или 2 (по вертикали, горизонтали и все возможных диагоналей) (игра крестики-нолики) в количестве n. Моя основная цель это крестики нолики на разных досках (определение победителя). И если там есть такое то возвращает 1 или 2

Я уже смог добиться определения победителя по вертикали и горизонтали, а вот по диагоналям уже 3-й день мозг ломаю, не как не получаеться ((

Добавлено через 5 минут
Всего диагоналей в матрице 3x4 = 3 + 4 - 1 = 6
Плюс соответственно 6 побочных диагоналей и того 12 которые нужно перебрать и в которых необходимо найти комбинацию из подряд чередующихся элементов. Как её так перебрать?

То есть нужно массив перебирать как ромбик, это вообще реально? Повернуть его на 45 градусов
Yandex
Объявления
29.06.2012, 21:16     Найти наиболее длинную цепочку в двумерном массиве
Ответ Создать тему
Опции темы

Текущее время: 16:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru