Szczegółowe omówienie zadania Marchewka:
Link do powyższego omówienia zadania Marchewka:
https://youtu.be/-6XSy1IUlgg?t=7010
https://youtu.be/-6XSy1IUlgg?t=7010
Możliwość wrzucania rozwiązań zadania Marchewka:
https://sio2.mimuw.edu.pl/c/zwo20/p/
https://sio2.mimuw.edu.pl/c/zwo20/p/
–
Zadanie Marchewka to zadanie które ćwiczy programowanie dynamiczne.
Zadanie dość zaawansowane i zrobienie tego zadania oznacza, że potrafimy robić już średnie/trudne zadania związane z programowaniem dynamicznym.
Polecam wykład Lecha Duraja dotyczący programowania dynamicznego w ramach Olimpiady Informatycznej Juniorów:
https://youtu.be/SBBDcyi7Y_g
—–
Jak się uczyć na podstawie takiego zadania?
https://tiny.pl/7x1gg
——-
Kod C++ programu Marchewka, który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int maxn = 2000;
int up[maxn+1][maxn+1],back[maxn+1][maxn+1],square[maxn+1][maxn+1];
string A[maxn+1];
int main()
{
int TT = 1;
while(TT--)
{
int n,m;
int M = 0;
cin >> n >> m;
for(int i=0; i<n; i++)
cin >> A[i];
for(int i=0; i<=max(m,n); i++)
up[i][0] = up[0][i] = back[i][0] = back[0][i] = square[i][0] = square[0][i] = 0;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
if (A[i-1][j-1]=='x')
square[i][j] = back[i][j] = up[i][j] = 0;
else
{
back[i][j] = back[i][j-1]+1;
up[i][j] = up[i-1][j]+1;
square[i][j] = min(min(back[i][j],up[i][j]),square[i-1][j-1]+1);
M = max(M,square[i][j]);
}
}
int c = 0;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
c+=(square[i][j]==M);
cout << M << " " << c << endl;
}
}