Omówienie zadania Marchewka / Programowanie dynamiczne

Szczegółowe omówienie zadania Marchewka:
Link do powyższego omówienia zadania Marchewka:
https://youtu.be/-6XSy1IUlgg?t=7010

Link do treści zadania Marchewka:
https://sio2.mimuw.edu.pl/c/zwo20/p/mar/
Możliwość wrzucania rozwiązań zadania Marchewka:
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;
  }
}
Link do pliku ze wzorcowym kodem C++ zadania Marchewka 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz