Миша і кукурудза (Розбір)

Аналіз алгоритму

Для зручності подальших обчислень перевернемо дошку знизу вгору. Клітинки по вертикалі та по горизонталі будемо нумерувати з $1$. Тоді маршрут мишки буде пролягати з лівого верхнього кута – клітинка з координатами $(1,1)$, у правий нижній – клітинку з координатами $(m,n)$. А рух вниз по дошці буде кодуватися літерою F.

Нехай на плитці з координатами $(i,j)$ знаходиться $a[i][j]$ зерняток. Нехай res[i][j] містить максимальну кількість зерняток, яку можна зібрати при русі з лівого верхнього кута в клітинку $(i,j)$. Оскільки на плитку $(i,j)$ можна потрапити або з плитки (i - 1, j), або з (i, j - 1), то

Можна також обійтися і без масиву res, здійснюючи обчислення в самому масиві а. Будемо проходити плитки підлоги (клітинки масиву) зверху вниз і зліва направо, поклавши

Спочатку всі клітинки нульового рядка та нульового стовпця масиву а ініціалізуємо -1. Однак для коректного перерахунку значення $a[1][1]$ слід обнулити одну з клітинок: $a[0][1]$ або $a[1][0]$. У такому випадку нове значення клітинки $a[1][1]$ стане рівним \max(a[0][1], a[1][0]) + a[1][1] = 0 + a[1][1] = a[1][1]. У подальшому всі значення $a[i][j]$ будуть перераховані коректно.

Після проведених обчислень $a[i][j]$ вже буде містити максимальну кількість зерняток, яку можна зібрати до досягнення плитки $(i,j)$. Стан масиву а за підсумками обчислень:

Реалізація алгоритму

Вхідну інформацію про зернятка будемо зберігати в масиві a. Тобто на плитці з координатами $(i,j)$ знаходиться $a[i][j]$ зерняток. Маршрут руху мишки будемо зберігати в масиві pos, що має довжину m + n - 1 ($m$ і $n$ – розміри підлоги).

#define MAX 102
int a[MAX][MAX];
char pos[2*MAX];

Зчитуємо вхідні дані. Оскільки на плитках може знаходитися і 0 зерняток, то ініціалізуємо клітинки масиву числами -1. Дошку перевертаємо знизу вгору.

scanf("%d %d",&m,&n);
memset(a,-1,sizeof(a));
for(i = 1; i <= m; i++)
    for(j = 1; j <= n; j++)
        scanf("%d",&a[m-i+1][j]);

Перерахуємо клітинки масиву а так, щоб $а[i][j]$ містило максимальну кількість зерняток, яку можна зібрати до досягнення плитки $(i,j)$.

a[0][1] = 0;
for(i = 1; i <= m; i++)
    for(j = 1; j <= n; j++)
        a[i][j] = max(a[i-1][j],a[i][j-1]) + a[i][j];

Починаючи з плитки (i, j) = (m, n), рухаємося до плитки $(1,1)$ записуючи маршрут руху мишки в масиві pos. З плитки $(i,j)$ необхідно рухатися в (i - 1, j) або (i, j - 1), залежно від того, яке зі значень a[i - 1][j] або a[i][j - 1] більше.

i = m; j = n; ptr = 0;
while(i + j > 2)
{
    if (a[i-1][j] > a[i][j-1])
    {
        pos[ptr] = 'F';
        i--;
    }
    else
    {
        pos[ptr] = 'R';
        j--;
    }
    ptr++;
}

Виводимо маршрут руху мишки.

while(ptr--) printf("%c",pos[ptr]);
printf("\n");