0

Прямо сейчас Альфу снится кошмар. В нем он бежит по дороге с препятствиями, на которой, ко всему прочему, разбросаны монеты. Дорога представляет из себя таблицу n × 3, в клетках которой либо ничего нет, либо находится стена, либо монета. Альф бежит вдоль стороны длиной n. Начинает он бежать из первой строки (то есть у него есть три варианта начала, он может выбрать любой из них) и бежит до тех пор, пока не врежется в стену, либо не пробежит дорогу целиком (не окажется в строчке n). Пусть сейчас Альф стоит в cтроке x и столбце y — (x; y), тогда он может попасть в три возможные клетки: (x + 1; y − 1), (x + 1; y), (x + 1; y + 1), если конечно новая клетка не выходит за пределы дороги, и в ней не находится стена. Так как все обитатели планеты Мелмак умеют контролировать свои сны, Альф смог получить карту дороги. Теперь он хочет узнать, какое наибольшее количество монет можно собрать к концу забега. Так как контроль сна отнимает у Альфа много сил, он просит вас написать программу, которая по карте сможет определить наибольшее количество монет, которое можно собрать за один забег.

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

В первой строке входного файла задано число n - количество строк в таблице. В следующих n строках дано по три символа , характеризующие данную строку таблицы. c равен «.», если клетка пустая, «C», если в этой клетке монета, и «W», если стена. Если в первой строке во всех клетках находятся стены, Альф заканчивает забег сразу.

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

В выходной файл выведите одно число — наибольшее количество монеток, которые можно собрать.

Пример

входные данные

W.W

C.C

WW.

CC.

CWW

вывод

3

мой код почему-то выводит 1 вместо 3

    #include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    char a[n][3];
    for (int i = 0; i < n; i++){
        for (int j =0; j < 3; j++){
            cin >> a[i][j];
        }
    }
    int res = 0;
    int mres = 0;
    if (a[n-1][0] == '.' || a[n-1][0] == 'C'){
        if(a[n-1][0] == 'C'){
            res++;
            a[n-1][0] = 'x';
        }
        else{
            a[n-1][0] = 'x';
        }
        for (int i = 0; i < n; i++){
            for (int j = 0; j < 3; j++){
                if (a[i][j] == 'x'){
                    if (a[i+1][j-1] == 'C' || a[i+1][j+1] == 'C' || a[i+1][j] == 'C'){
                        if (a[i+1][j+1] == 'C'){
                            a[i][j] = '.';
                            res++;
                            a[i+1][j+1] = 'x';
                        }
                        if (a[i+1][j] == 'C'){
                            a[i][j] ='.';
                            res++;
                            a[i+1][j] = 'x';
                        }
                        if (a[i+1][j-1] == 'C'){
                            a[i][j] = '.';
                            res++;
                            a[i+1][j-1] = 'x';
                        }
                    }
                    else {
                         if (a[i+1][j+1] != 'W'){
                            a[i][j] = '.';
                            
                            a[i+1][j+1] = 'x';
                        }
                        if (a[i+1][j] != 'W'){
                            a[i][j] ='.';
                           
                            a[i+1][j] = 'x';
                        }
                        if (a[i+1][j-1] != 'w'){
                            a[i][j] = '.';
                            
                            a[i+1][j-1] = 'x';
                        }
                        
                    }
                }
            }
        }
    }
    mres = res;
    cout << mres;
    

    return 0;
}

1 ответ 1

2

Может, чего и недосмотрел — без URL проверялки сложно на глаз говорить... — но "на коленке" вот такое вот написалось:

#include <algorithm>
#include <string>
#include <iostream>

using namespace std;

int getmax(int i, int v[3])
{
    if (i == 0) return max(v[0],v[1]);
    else if (i == 1) return max(max(v[0],v[1]),v[2]);
    return max(v[2],v[1]);
}

int main()
{
    int n, prev[3] = {0}, next[3] = {0}, m = 0;
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        string z;
        cin >> z;
        for(int j = 0; j < 3; ++j)
        {
            if (z[j] == 'W') next[j] = -n;
            else if ((next[j] = getmax(j,prev)) != -n)
                next[j] += (z[j] == 'C');
        }
        int v = max(next[0],max(next[1],next[2]));
        for(int j = 0; j < 3; ++j) prev[j] = next[j];
        if (v == -n) break;
        m = v;
    }
    cout << m;
}

Есть один непонятный момент — должен ли он бежать как можно дальше, или как можно дороже? Например,

WWWWW......C
......WWWWWW
WWWWWCCCWWWW

Что тут — 3 или 1? Мое решение относиться к варианту 1 — т.е. бежать как можно дальше. Если "дороже" — то надо дополнительно запоминать текущий максимум, из которого уже некуда добраться, и запоминать его.

Update

Ну, если, как написали в комментариях, надо именно побольше собрать, то надо изменить 3 строчки.

int n, prev[3] = {0}, next[3] = {0}, m = 0, M = 0;

m = v; M = max(m,M);

и в конце

cout << M;
2
  • Альф - алчный.(Теперь он хочет узнать, какое наибольшее количество монет можно собрать к концу забега. ) Ему все равно к чему приведет его любовь к деньгам, т.е. фактор бежать как можно дальше для него менее важен.
    – TigerTV.ru
    7 июл 2022 в 15:07
  • 1
    @TigerTV.ru OK, будь по-вашему :) См. дополнение к ответу.
    – Harry
    7 июл 2022 в 15:24

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.