Черепашка - C++

273

14 марта 2017, 15:46

Что я не правильно делаю в этой задаче? Помогите пожалуйста!

В таблице размером N*N клетки заполнены случайным образом числами от –100 до 100. Напишите программу, которая поможет черепашке найти маршрут из самой нижней левой клетки в самую верхнюю правую клетку и удовлетворяющий следующим условиям:

Если клетки таблицы перенумеровать сверху вниз и слева направо, то из клетки (i,j) (i - строка, j - столбец) черепашка может перейти в клетки вверх - (i–1,j), вправо вверх - (i–1,j+1) и вправо - (i,j+1), не выходя, конечно, за границы таблицы.

Нужно найти маршрут с максимальной суммой чисел в клетках маршрута.

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

В первой строке входных данных задано одно натуральное число N (N <= 100). В следующих N строках заданы числа в клетках таблицы.

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

Одно число – максимальная сумма в клетках искомого маршрута.

Информация
Лимит времени: 1 секунды
Предел памяти: 64 Mb
Баллы: 10
Уровень сложности: 6/67 (91 %)

Пример
Пример входных данных

Пример выходных данных: 27

int a[MAXN][MAXN];
int d[MAXN][MAXN];
int main()
{
    int n;
    scanf("%d", &n);
    memset(a, -1, sizeof(a));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    d[n][1] = a[n][1];
    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= n; j++)
        {
            d[i][j] = max(d[i][j + 1], max(d[i - 1][j + 1],
                                           d[i - 1][j])) + a[i][j];
            // cout<<max(a[i][j+1],a[i-1][j+1])<<endl;
        }
    printf("%d", d[n][n]);

Answer 1

Откровенно говоря, разбираться лень; похоже, вы не в том направлении смотрите клетки, откуда попадаете в данную, а кроме того, не рассматриваете случаи, когда попасть в данную клетку просто неоткуда.

Попробуйте посмотреть отсюда:

int main()
{
    unsigned int N;
    cin >> N;
    vector<vector<int>> a(N,vector<int>(N,0));
    vector<vector<int>> d(N,vector<int>(N,0));
    for(int r = 0; r < N; r++)
        for(int c = 0; c < N; c++) cin >> a[r][c];
    for(int r = N-1; r >= 0; r--)
    {
        for(int c = 0; c < N; c++)
        {
            d[r][c] = a[r][c];
            int v = numeric_limits<int>::min();
            if (c-1 >= 0)
            {
                if (v < d[r][c-1]) v = d[r][c-1];
            }
            if (r+1 < N)
            {
                if (v < d[r+1][c]) v = d[r+1][c];
            }
            if ((c-1 >= 0) && (r+1 < N))
            {
                if (v < d[r+1][c-1]) v = d[r+1][c-1];
            }
            if (v != numeric_limits<int>::min())
            {
                d[r][c] += v;
            }
        }
    }
    cout << d[0][N-1] << endl;
}

И еще - как-то у вас задача изложена сумбурно. Обычно сначала в координатах идет x, потом y, у вас - сначала строка, потом столбец... То Чебурашка, то черепашка :)

Словом, мне пришлось плясать от решения. а не от задачи :(

Answer 2

Вы, очевидно, выбрали способ нумерации [i][j] (i - строка, а j - столбец), в котором строки нумеруются сверху-вниз, а столбцы - слева-направо.

Тогда ваши циклы заполняют матрицу d в порядке слева-направо снизу-вверх. То есть матрица d инициализируется вычисленными значениями из левого-нижнего угла наружу.

Но при этом на каждой итерации ваша формула

d[i][j] = max(d[i][j + 1], max(d[i - 1][j + 1], d[i - 1][j])) + a[i][j];

проверяет правых и верхних соседей текущей точки. Но эти элементы матрицы d еще не получили осмысленные значения! Там сидят начальные нули.

Ваша формула развернута не в ту сторону. При вычислении d[i][j] надо смотреть назад, на уже пройденную часть матрицы, а не вперед на "пустую" часть. При выбранном вами способе нумерации вам нужно вычислять значение элемента d[i][j] на основе анализа уже вычисленных значений d[i][j - 1], d[i + 1][j - 1] и d[i + 1][j]:

d[i][j] = max(d[i][j - 1], max(d[i + 1][j - 1], d[i + 1][j])) + a[i][j];

Ну и, разумеется, при выбранном вами способе нумерации печатать в самом конце вам надо d[1][n], а не d[n][n].

Также, как правильно заметил @Harry, так как входные значения могу быть отрицательными, для того, чтобы использовать крайние элементы матрицы в качестве guard elements, нам не подходит значение 0 в этих элементах. Нам нужно чтобы они содержали некое "очень маленькое значение", т.е. не влияли на вычисление максимума.

То есть следует еще изначально проинициализировать d следующим образом

d[n + 1][0] = 0;
for (int i = 1; i <= n; ++i)
  d[i][0] = INT_MIN; // std::numeric_limits<int>::min();
for (int j = 1; j <= n; ++j)
  d[n + 1][j] = INT_MIN; // std::numeric_limits<int>::min();

(Элемент d[n + 1][0] умышленно проинициализирован нулем).

http://coliru.stacked-crooked.com/a/71b7165e3a1ea87e