Conteúdos Utilizados:
Primeiro, é necessário notar que, para a máquina ser capaz de colher um ponto 
, 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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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); | |
| } |