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

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

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

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

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

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

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

В целочисленном массиве найти наиболее длинную цепочку одинаковых подряд стоящих элементов - C++
В целочисленном массиве найти наиболее длинную цепочку одинаковых подряд стоящих элементов (вывести на экран длину такой цепочки и элемент...

В одномерном массиве найти самую длинную цепочку подряд стоящих элементов, которая является «палиндромом» - C++
в одномерном массиве найти самую длинную цепочку подряд стоящих элементов, которая является «палиндромом». В такой цепочке первое число...

Цикл: Найти самую длинную неубывающую цепочку чисел - C++
В цикле с клавиатуры вводится 15 целых чисел. Необходимо найти самую длинную неубывающую цепочку чисел. На экран вывести найденную...

Найти самую длинную возрастающую цепочку простых чисел - C++
Привет всем Решаю задачку: Найти самую длинную возрастающую цепочку простых чисел В заданном бинарном файле необходимо ...

Найти в матрице самую длинную цепочку подряд стоящих 0 по горизонтали или вертикали - C++
Матрица состоит из 0 и 1. Найти в ней самую длинную цепочку подряд стоящих 0 по горизонтали или вертикали. Для ориентации поиска...

найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц - C++
Нужно найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц. В чем ошибка ? #include <iostream> #include...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
zitxbit
Master C/C++
88 / 740 / 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++
88 / 740 / 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++
88 / 740 / 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++
88 / 740 / 75
Регистрация: 11.04.2012
Сообщений: 971
29.06.2012, 21:07 #8
Точнее сейчас немогу, занят.

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

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

Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц - C++
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц. Входные данные: В единственной строке...

Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц - C++
Здравствуйте, не могу понять в чём может быть ошибка :) Решаю олимпиадную задачу. Но система находит в тесте 5 не верный ответ) В...

В последовательности найти наиболее длинную последовательность подряд идущих нулей - C++
Дана последовательность из n вещественных чисел. Найти наиболее длинную последовательность подряд идущих нулей.

Матрица L(n,k) состоит из нулей и единиц. Найти в ней самую длинную цепочку подряд стоящих нулей по горизонтал - C++
Помогите решить на C++ QtCreator


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
29.06.2012, 21:16
Ответ Создать тему
Опции темы

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