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

Для зручності подальших обчислень перевернемо дошку знизу вгору. Клітинки по вертикалі та по горизонталі будемо нумерувати з $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");