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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
p.pavluxa
1 / 1 / 0
Регистрация: 30.07.2011
Сообщений: 15
#1

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

29.06.2012, 17:31. Просмотров 698. Ответов 9
Метки нет (Все метки)

Здравствуйте. Помогите пожалуйста решить одну задачку на любом языке программировании (желательно PHP): в целочисленном двумерном массиве найти наиболее длинную цепочку одинаковых подряд стоящих элементов (кроме нуля) по вертикали либо горизонтали либо по диагонали (основной и побочной). Вернуть длину этой цепочки и элемент её составляющей.

Пожалуйста, уже всю голову сломал.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.06.2012, 17:31     Найти наиболее длинную цепочку в двумерном массиве
Посмотрите здесь:
В целочисленном массиве найти наиболее длинную цепочку одинаковых подряд стоящих элементов C++
C++ В одномерном массиве найти самую длинную цепочку подряд стоящих элементов, которая является «палиндромом»
Найти самую длинную возрастающую цепочку простых чисел C++
Цикл: Найти самую длинную неубывающую цепочку чисел C++
Найти в матрице самую длинную цепочку подряд стоящих 0 по горизонтали или вертикали C++
найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц C++
C++ Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zitxbit
Master C/C++
87 / 739 / 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++
87 / 739 / 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++
87 / 739 / 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++
87 / 739 / 75
Регистрация: 11.04.2012
Сообщений: 971
29.06.2012, 21:07     Найти наиболее длинную цепочку в двумерном массиве #8
Точнее сейчас немогу, занят.

Добавлено через 2 минуты
Если кол-во строк или столбцов прямоугольн. матрицы нечетные, то разбить ее на квадраты будет сложно, поскольку будут отдельные строки или столбцы которые оставшиеся при делении. Вообще-то, это большой проект.
Nick Alte
Эксперт С++
1608 / 1000 / 118
Регистрация: 27.09.2009
Сообщений: 1,927
Завершенные тесты: 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++
Матрица L(n,k) состоит из нулей и единиц. Найти в ней самую длинную цепочку подряд стоящих нулей по горизонтал C++
В заданной строке найти наиболее длинную подстроку чередующихся цифр и букв C++
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     Найти наиболее длинную цепочку в двумерном массиве
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru