2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Ошибка в программе [C++]
Сообщение30.09.2018, 17:09 
Программа необходима для решения первой задачи отсюда: https://yadi.sk/i/xSlQVCrokFAqcQ
Моя попытка решения:
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <cstdio>
#include <cstring>
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T;
    scanf("%d", &T);
    for(int i=1; i<=T; ++i)    // число циклов = числу указанному в первой строке input.txt
    {
        int H, W;
        scanf("%d%d", &H, &W); // H-высота и W-ширина таблицы
        char LRUD[101];        // символьный массив на 100 символов + символ конца строки
        scanf("%s", LRUD);
        int ARR[100][100];
        for(int i=0; i<H; ++i)
            for(int j=0; j<W; ++j)
                scanf("%d", &ARR[i][j]);       // заполнение двумерного массива
        for(int i=0; i<H; ++i)
        {
            for (int j = 0; j < W; ++j)
            {
                int s = ARR[i][j], i1=i, j1=j;  // начало главного блока
                for (int k = 0; k < strlen(LRUD); ++k)
                {
                    if (LRUD[k] == 'L')
                    {
                        j1=j1-1;
                        s = s + ARR[i1][j1];
                        if(j1<0) s=-2000000000; // если выход за пределы таблицы
                    }                           // то переменной присваивается отрицательное значение
                    if (LRUD[k] == 'R')         // заведомо превосходящее сумму положительных
                    {
                        j1=j1+1;
                        s = s + ARR[i1][j1];
                        if(j1>=W) s=-2000000000;
                    }
                    if (LRUD[k] == 'U')
                    {
                        i1=i1-1;
                        s = s + ARR[i1][j1];
                        if(i1<0) s=-2000000000;
                    }
                    if (LRUD[k] == 'D')
                    {
                        i1=i1+1;
                        s = s + ARR[i1][j1];
                        if(i1>=H) s=-2000000000;
                    }                                      // конец главного блока
                }
                if (s>0) printf("%d ", s);                 // вывод только чисел полученных без выхода
                else printf("%d ", 0);                     //за пределы таблицы, иначе ноль
            }
            printf("\n");                                  // разбиение единой строки на подстроки
        }
    }
    return 0;
}


На двух примерах в PDF файле моя программы выдаёт верный ответ. В системе тестирования проходит два теста, но на третьем выдаёт неверный результат. Содержание теста мне не известно. Возможно неверный ответ возникает в экстремальных случаях, типа 100 тестовых случаев, в каждом тестовом случае по 100000 клеток, в каждой клетке трёхзначное число

 
 
 
 Re: Ошибка в программе
Сообщение30.09.2018, 17:39 
SpiderHulk в сообщении #1342630 писал(а):
Используется синтаксис C++
s = s + ARR[i1][j1];
if(i1<0) s=-2000000000;
А разве можно обращаться в массив по отрицательному индексу?!
Аналогично для другой переменной и для проверки на максимум.
Просто первое что бросилось в глаза.

 
 
 
 Re: Ошибка в программе
Сообщение30.09.2018, 18:36 
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <cstdio>
#include <cstring>
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T;
    scanf("%d", &T);
    for(int i=1; i<=T; ++i)
    {
        int H, W;
        scanf("%d%d", &H, &W);
        char LRUD[101];  
        scanf("%s", LRUD);
        int ARR[100][100];
        for(int i=0; i<H; ++i)
            for(int j=0; j<W; ++j)
                scanf("%d", &ARR[i][j]);    
        for(int i=0; i<H; ++i)
        {
            for (int j = 0; j < W; ++j)
            {
                int s = ARR[i][j], i1=i, j1=j;
                for (int k = 0; k < strlen(LRUD); ++k)
                    {
                        if (LRUD[k] == 'L')
                        {
                            j1=j1-1;
                            if (j1>=0) s = s + ARR[i1][j1];
                            else s=-2000000000;
                        }            
                        if (LRUD[k] == 'R')
                        {
                            j1=j1+1;
                            if(j1<W) s = s + ARR[i1][j1];
                            else s=-2000000000;
                        }
                        if (LRUD[k] == 'U')
                        {
                            i1=i1-1;
                            if(i1>=0) s = s + ARR[i1][j1];
                            else s=-2000000000;
                        }
                        if (LRUD[k] == 'D')
                        {
                            i1=i1+1;
                            if(i1<H) s = s + ARR[i1][j1];
                            else s=-2000000000;
                        }              
                    }
                    if (s>0) printf("%d ", s);              
                    else printf("%d ", 0);                  
            }
            printf("\n");                      
        }
    }
    return 0;
}


Исправил, теперь на тесте №4 Run-time Error - решение вернуло код ошибки, отличный от нуля.

 
 
 
 Re: Ошибка в программе
Сообщение30.09.2018, 19:20 
SpiderHulk
Что будет если начальная координата x=0, потом делаются шаги минус, минус и плюс? После двух минусов координата станет x=-2, при попытке шага плюс координата станет x=-1, условие x<W вполне себе выполняется и происходит обращение в массив с индексом -1 ... Можно даже короче: из крайней левой клетки шаг влево и потом шаг вверх или вниз - при нём проверяемое условие выполняется и обращение в массив с отрицательным индексом. Аналогично со всеми четырьмя шагами.
Подсказка: надо или проверять все 4 условия на координаты до обращения в массив или вообще при обнаружении выхода за поле выходить из цикла проверки клетки с нулём на выходе и переходить к следующим i,j. Или ещё как-то, вариантов много.

 
 
 
 Re: Ошибка в программе
Сообщение01.10.2018, 07:08 
Dmitriy40
Спасибо, проблема решена

 
 
 
 Re: Ошибка в программе
Сообщение01.10.2018, 13:53 
Для каждого квадрата выполнять разбор строки с маршрутом (LRUD) не выглядит оптимальным.
Лучше один раз разобрать эту строку заполнив список с координатами (относительно стартового (0, 0)) посещаемых квадратов, одновременно при этом вычисляя границы (относительные) прямоугольного региона «блужданий». Это позволит сразу определить квадраты, старт из которых приведёт к выходу за границы поля или быстро вычислить требуемую сумму в противном случае.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group