Problema obtido das provas de seleção das Olimpíadas Nacionais de Informática (ONI) de 2022 (deve ser consultado o endereço incluso):
"As ONI estão a desenvolver um carro automático. Para testar o carro as ONI têm uma grelha quadrada de N por N onde o carro se movimenta entre células. Quando o carro está numa célula (x, y) só se pode movimentar para as células (x + 1, y) e (x, y + 1). Adicionalmente, há K células inacessíveis, sobre as quais o carro não pode estar. É garantido que as células (1, 1) e (N, N) são sempre acessíveis.
A figura seguinte ilustra um exemplo de uma grelha de 3 por 3 com duas células inacessíveis:
Para testar o carro é importante saber o número de caminhos distintos que o carro pode fazer começando na célula (1, 1) e terminando na célula (N, N) que evitam as K células inacessíveis. Como o número de caminhos pode ser muito grande, deves calcular a resposta módulo 109 + 7.
Para o exemplo da figura anterior existem dois caminhos distintos:
O Problema
Dadas as dimensões N de uma grelha e um conjunto de K células inacessíveis, calcula o número de caminhos distintos de (1, 1) até a (N, N) módulo 109 + 7".
"ONI are developing an automatic car. To test the car the ONI have a square grid N of N where the car moves between cells. When the car is in a cell (x, y) can only move to cells (x + 1, y) and (x, y + 1). Additionally, there are in inaccessible K cells, on which the car cannot be. It is guaranteed that cells (1, 1) and (N, N) are always accessible.
The following figure illustrates an example of a 3 by 3 grid with two inaccessible cells:
To test the car it is important to know the number of distinct paths that the car can make starting in the cell (1, 1) and ending in the cell (N, N) that prevent K inaccessible cells. As the number of paths can be very large, you must calculate the response module 109 + 7.
For the example of the previous figure there are two distinct paths:
The problem
Given the N dimensions of a grid and a set of inaccessible K cells, calculates the number of distinct paths from (1, 1) to (N, N) module 109 + 7".