Уменьшить время выполнения программы

@Desking · Регистрация: 01.03.2016

Студворк — интернет-сервис помощи студентам

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
#include <iostream>
 
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    char mas[n][n];
    int k;
    int z;
    int g = 0;
    int v = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> mas[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (mas[i][j] == '-') k++;
            else {
                if (k >= 2) g++;
                k = 0;
 
            }
            if (mas[j][i] == '-') z++;
            else {
                if (z >= 2) v++;
                z = 0;
            }
 
        }
        if (k >= 2) g++;
        if (z >= 2) v++;
        k = 0;
        z = 0;
    }
    cout << g << " " << v;
 
 
    return 0;
}

Нужно сократить время выполнения программы, сейчас оно 306 ms, а нужно меньше 256 ms

Добавлено через 5 минут
ой, меньше 300 ms

Добавлено через 1 минуту
Вам дано квадратный кроссворд размера NxN. Пустые клетки обозначены в нем символом '-', закрашены - символом '#'. По правилам кроссвордов, каждое слово должно состоять минимум из 2 букв.
Вам нужно для данного кроссворда посчитать количество слов по горизонтали и по вертикали.
Входные данные:
В первой строке содержится число N (1 ≤ N ≤ 2000) - размер кроссворда.
Следующие N строк содержат кроссворд. Каждая строка состоит из N символов '-' и '#', описанных выше.

Исходные данные:
Выведите два числа - количество слов по горизонтали и по вертикали.

Входные данные

5
----#
--##-
-----
-##--
#----

Результат работы

5 4

@LetoLetoD · 09.04.2016, 16:36

Если время заполнения массива учитывается, то так будет чуть быстрее.

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
#include <iostream>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    char mas;
    int k = 0;
    int z[n];
    int g = 0;
    int v = 0;
    for (int i = 0; i < n; i++) {
        z[i] = 0;
        for (int j = 0; j < n; j++) {
            cin >> mas;
            if (mas == '-') k++;
            else {
                if (k >= 2) g++;
                k = 0;
            }
            if (mas == '-') z[i]++;
            else {
                if (z[i] >= 2) v++;
                z[i] = 0;
            }
        }
        if (k >= 2) g++;
        if (z[i] >= 2) v++;
        k = 0;
    }
    cout << g << " " << v;
    return 0;
}

@Serg_o_Grey · 09.04.2016, 19:39

LetoLetoD, у вас результат другой

Добавлено через 8 минут
Desking, а у вас k и z не инициализированы в 10 и 11 строчках

@RQdan · 09.04.2016, 23:46

Desking, представлю и свой вариант обработки во время ввода данных.
Надеюсь, это немного ускорит программу

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
#include <iostream>
 
using namespace std;
 
void main() {
    int n;
    cin >> n;
    int wordsG = 0;
    int wordsV = 0;
    char** mas;
    int* masv;
 
    mas = new char*[n];
    masv = new int[n];
    for(int i = 0; i < n; i ++) {
        masv[i] = 0;
        mas[i] = new char[n];
    }
 
    for (int i = 0; i < n; i++) {
        int g = 0;
        for (int j = 0; j < n; j++) {
            cin >> mas[i][j];
            if(mas[i][j] == '-') {
                g++;
                masv[j]++;
            }
            else {
                if (g > 1) {
                g = 0;
                wordsG++;
                }
                else g = 0;
                if(masv[j] > 1) {
                    masv[j] = 0;
                    wordsV++;
                }
                else masv[j] = 0;
            }           
        }
        if(g > 1) wordsG++;
    }
    for(int i = 0; i < n; i++) {
        if(masv[i] > 1) wordsV++;
    }
    cout<<wordsG<<" "<<wordsV<<endl;
 
    for(int i = 0; i < n; i++) delete []mas[i];
    delete []mas;
    delete []masv;
}

@LetoLetoD · 10.04.2016, 01:39

Serg_o_Grey, действительно. Поленился, не проверил

Тогда так:

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
#include <iostream>
using namespace std;
int main() {
    int n;
        cin >> n;
    char mas;
    int k = 0;
    int z[n] = {0};
    int g = 0;
    int v = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> mas;
            if (mas == '-')
            {
                k++;
                z[j]++;
            }
            else {
                if (k > 1) 
                    g++;
                k = 0;
                if (z[j] > 1) 
                    v++;
                z[j] = 0;
            }
        }
        if (k > 1) g++;
        k = 0;
    }
    for (int j = 0; j < n; j++)
        if (z[j] > 1)
                    v++;
    cout << g << " " << v;
    return 0;
}

@Mr.X · 10.04.2016, 07:53

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
//Вам дано квадратный кроссворд размера NxN. Пустые клетки обозначены в нем символом '-',
//закрашены - символом '#'. По правилам кроссвордов, каждое слово должно состоять минимум
//из 2 букв.
//Вам нужно для данного кроссворда посчитать количество слов по горизонтали и по вертикали.
//Входные данные:
//В первой строке содержится число N (1 ≤ N ≤ 2000) - размер кроссворда.
//Следующие N строк содержат кроссворд. Каждая строка состоит из N символов '-' и '#',
//описанных выше.
 
//Исходные данные:
//Выведите два числа - количество слов по горизонтали и по вертикали.
 
//Входные данные
 
//5
//----#
//--##-
//-----
//-##--
//#----
 
//Результат работы
 
//5 4
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    const   int         N_MAX           =   2000;
 
    const   char        BLACK_CELL      =   '#';
 
    const   unsigned    VERT_FLAG       =   1U;
    const   unsigned    HORIZ_FLAG      =   2U;
 
    char                line_prev       [N_MAX];
    char                line_cur        [N_MAX];
 
    int                 vert_count      {};
    int                 horiz_count     {};
 
    int                 n               {};
 
    std::cin    >>  n;
 
    for ( int i{}; i < n; ++i )
    {
        for ( int j{}; j < n; ++j )
        {
            std::cin >> line_cur[j];
 
            if  (
                    line_cur[j]     ==  BLACK_CELL
                )
            {
                continue;
            }
 
            line_cur[j]             =   0;
 
            bool    is_start_vert   =       i                   ==  0
                                        ||  line_prev[j]        ==  BLACK_CELL;
 
            bool    is_start_horiz  =       j                   ==  0
                                        ||  line_cur[j - 1]     ==  BLACK_CELL;
 
            if( is_start_vert )
            {
                line_cur[j]     |=  VERT_FLAG;
            }
            else if (
                        line_prev[j]    &   VERT_FLAG
                    )
            {
                ++vert_count;
            }//else if
 
            if( is_start_horiz )
            {
                line_cur[j]     |=  HORIZ_FLAG;
            }
            else if (
                        line_cur[j - 1]     &   HORIZ_FLAG
                    )
            {
                ++horiz_count;
            }//else if
        }//for j
 
        std::swap
            (
                line_cur,
                line_prev
            );
    }//for i
 
    std::cout   <<  std::endl
                <<  horiz_count
                <<  '\t'
                <<  vert_count
                <<  std::endl;
}

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@Serg_o_Grey 116 / 106 / 51 Регистрация: 29.03.2016 Сообщений: 480
	09.04.2016, 19:39
	LetoLetoD, у вас результат другой Добавлено через 8 минут Desking, а у вас k и z не инициализированы в 10 и 11 строчках 0