2017. Jeu de grille

2017. Jeu de grille

Difficulté : moyenne

Sujets :Tableau,Matrice,Somme du préfixe

Vous recevez un tableau 2D indexé 0grillede taille2xn, oùgrille[r][c]représente le nombre de points à la position(r,c)sur la matrice. Deux robots jouent à un jeu sur cette matrice.

Les deux robots démarrent initialement à(0, 0)et je veux atteindre(1, n-1). Chaque robot ne peut se déplacer que vers la droite ((r,c)à(r, c + 1)) ou vers le bas ((r,c)à(r + 1,c)).

Au début du jeu, le premier robot se déplace de(0, 0)à(1, n-1), collectant tous les points des cellules sur son chemin. Pour toutes les cellules(r,c)parcouru sur le chemin,grille[r][c]est réglé sur0. Ensuite, le deuxième robot passe de(0, 0)à(1, n-1), récupérant les points sur son chemin. Notez que leurs chemins peuvent se croiser.

Le premier robot souhaite minimiser le nombre de points collectés par le deuxième robot. En revanche, le deuxième robot souhaite maximiser le nombre de points qu’il collecte. ...
[Courte citation de 8% de l'article original]