Conteúdos Utilizados:
Primeiro, é necessário notar que, para a máquina ser capaz de colher um ponto $$(i, j)$$, a distância do menor caminho entre a posição inicial da máquina deve ser menor que ou igual à menor distancia entre qualquer posição de musgos inicialmente, ou a máquina deve ser capaz de alcançar o ponto, enquanto nenhum musgo o alcança. Além disso, o ponto deve estar no maior caminho que a máquina consegue percorrer.
Podemos então utilizar a técnica de Multisource BFS, ou seja, iniciar a fila da BFS com vários vértices. Podemos usar uma BFS partindo de todos os musgos no inicio, e encontrar assim, a menor distancia de qualquer ponto que pode ser alcançado por musgos, ao musgo mais próximo. Então, executamos uma BFS partindo da máquina, e encontramos a menor distância de cada ponto alcançável, em relação a máquina. Então, verificamos todos os pontos no grid, e o ponto com a maior distancia da colheitadeira, que seja menor que ou igual a distancia do musgo mais próximo.
Segue o código, comentado, para melhor entendimento.
| #include<bits/stdc++.h> | |
| using namespace std; | |
| const int INF = 1e9; | |
| int distMS[512][512], dist[512][512]; | |
| int marc[512][512], marcms[512][512]; | |
| int orig[512][512]; | |
| int n, m; | |
| int dx[5] = {1, 0, -1, 0}; | |
| int dy[5] = {0, 1, 0, -1}; | |
| vector< pair<int, int> > musgos; | |
| void bfsMS(){ | |
| queue<pair<int, int> > q; | |
| memset(distMS, INF, sizeof(distMS)); //inicializamos todas as distancias em relacao aos musgos como infinito | |
| //inserimos todas as posicoes iniciais de musgos na fila da BFS | |
| for(int i = 0; i < musgos.size(); i++){ | |
| marcms[musgos[i].first][musgos[i].second] = 1; | |
| distMS[musgos[i].first][musgos[i].second] = 0; | |
| q.push(musgos[i]); | |
| } | |
| while(!q.empty()){ | |
| int i = q.front().first; | |
| int j = q.front().second; | |
| q.pop(); | |
| for(int k = 0; k < 4; k++){ | |
| int ii = i + dx[k]; | |
| int jj = j + dy[k]; | |
| //se o ponto vizinho existe, nao e uma pedra e nao foi marcado, o-inserimos na fila | |
| if(ii < 0 || ii >= n || jj < 0 || jj >= m || marcms[ii][jj] || orig[ii][jj] == 1) continue; | |
| distMS[ii][jj] = distMS[i][j] + 1; | |
| marcms[ii][jj] = 1; | |
| q.push(make_pair(ii,jj)); | |
| } | |
| } | |
| } | |
| void bfs(int i1, int j1){ | |
| queue<pair<int, int> > q; | |
| memset(dist, INF + 10, sizeof(distMS)); | |
| q.push(make_pair(i1, j1)); | |
| dist[i1][j1] = 0; | |
| marc[i1][j1] = 1; | |
| while(!q.empty()){ | |
| int i = q.front().first; | |
| int j = q.front().second; | |
| q.pop(); | |
| for(int k = 0; k < 4; k++){ | |
| int ii = i + dx[k]; | |
| int jj = j + dy[k]; | |
| //se o ponto vizinho existe, nao e uma pedra e nao foi marcado, o-inserimos na fila | |
| if(ii < 0 || ii >= n || jj < 0 || jj >= m || marc[ii][jj] || orig[ii][jj] == 1) continue; | |
| dist[ii][jj] = dist[i][j] + 1; | |
| marc[ii][jj] = 2; | |
| q.push(make_pair(ii,jj)); | |
| } | |
| } | |
| } | |
| int inii, inij; | |
| int main(){ | |
| scanf("%d %d", &n, &m); | |
| for(int i = 0; i < n; i++){ | |
| for(int j = 0; j < m; j++){ | |
| char c; | |
| scanf(" %c", &c); | |
| if(c == 'P') orig[i][j] = 1; | |
| if(c == 'O') musgos.push_back(make_pair(i, j)); | |
| if(c == 'C') inii = i, inij = j; | |
| } | |
| } | |
| bfsMS(); | |
| bfs(inii, inij); | |
| int ans = -1; | |
| for(int i = 0; i < n; i++){ | |
| for(int j = 0; j < m; j++){ | |
| if(marc[i][j] == 2){ | |
| if(dist[i][j] <= distMS[i][j] || !marcms[i][j]){ | |
| ans = max(ans, dist[i][j]); | |
| // encontramos a maior distancia valida, que será a resposta. | |
| } | |
| } | |
| } | |
| } | |
| printf("%d\n",ans + 1); | |
| } |
