# Patrol2 30/100 BFS

**URL:** <https://forum.olinfo.it/t/patrol2-30-100-bfs/8521>\
**Category:** Aiuto\
**Created:** [6 Ottobre 2023, 7:28am UTC](https://forum.olinfo.it/t/patrol2-30-100-bfs/8521 "2023-10-06T07:28:29Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![TommasoTode](https://forum.olinfo.it/user_avatar/forum.olinfo.it/tommasotode/32/2896_2.png) [@TommasoTode](https://forum.olinfo.it/u/TommasoTode)\
**Post date:** [6 Ottobre 2023, 7:28am UTC](https://forum.olinfo.it/t/patrol2-30-100-bfs/8521/1 "2023-10-06T07:28:29Z")

</div>

Sto cercando di risolvere patrol2 con una BFS leggermente modificata.  
Passano tutti i testcase apparte al 004 e dal 016 al 021.  
L’approccio è una BFS che ogni volta che nei neighbours trova un vertex con una guardia fa distanza++.  
Ovviamente ho dovuto togliere il visited per l’uscita, in modo da ricalcolare il percorso da tutti i vicini e trovare quello minimo.

Penso di essermi dimenticato qualche edgecase particolare, ma non mi viene in mente cosa potrebbe essere.

```auto
#include <fstream>
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

class Graph
{
public:
	int N = 0;
	vector<vector<int>> adj;

	Graph(int n)
	{
		adj.resize(n);
		N = n;
	}
	
	void addEdge(int v, int w)
	{
		adj[v].push_back(w);
		adj[w].push_back(v);
	}	

	int BFS(int exit, vector<int> policepath)
	{
		queue<int> queue;
		vector<bool> visited(N, false);
		vector<int> distance(N, INT_MAX);
		int min_path = INT_MAX;

		visited[0] = true;
		distance[0] = 0;
		queue.push(0);
		while (!queue.empty())
		{
			int s = queue.front(); queue.pop();
			for (auto v : adj[s])
			{
				if (visited[v]) continue;
				distance[v] = distance[s] + 1;

				int police_index = (distance[v] % policepath.size());
				bool occupied = (v == policepath[police_index]);

				if (occupied)
					distance[v]++;
				
				if (v == exit)
					min_path = min(min_path, distance[v]);
				else
					visited[v] = true;

				queue.push(v);
			}
		}
		return min_path;
	}
};

int main()
{
	int N, M, L;
	cin >> N >> M >> L;
	vector<int> A(M), B(M);
	for (int i = 0; i < M; ++i) cin >> A[i] >> B[i];
	vector<int> C(L);
	for (auto &x : C) cin >> x;

	Graph g = Graph(N);
	for(int i = 0; i < M; i++)
		g.addEdge(A[i], B[i]);

	cout << g.BFS(N-1, C) << endl;
	return 0;
}

```

Grazie in anticipo per l’aiuto 🙂 .

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [6 Ottobre 2023, 10:36am UTC](https://forum.olinfo.it/t/patrol2-30-100-bfs/8521/2 "2023-10-06T10:36:45Z")

</div>

Con questo input:  
7 8 3  
5 4  
4 0  
3 5  
5 1  
1 2  
3 1  
2 6  
3 2  
4 3 5  
il programma restituisce min\_path = 7, mentre la risposta corretta è 6.

---

<div class="post-metadata">

**Author:** ![TommasoTode](https://forum.olinfo.it/user_avatar/forum.olinfo.it/tommasotode/32/2896_2.png) [@TommasoTode](https://forum.olinfo.it/u/TommasoTode)\
**Post date:** [6 Ottobre 2023, 2:00pm UTC](https://forum.olinfo.it/t/patrol2-30-100-bfs/8521/3 "2023-10-06T14:00:50Z")

</div>

Grazie mille. Ho capito il problema. Con una BFS non posso prioritizzare il percorso minore dato che la ricerca viene fatta prioritizzando i valori aggiunti prima nell’adjacency list, che sono pressoché casuali, o meglio dipendono dall’input.

 ![grafo](https://forum.olinfo.it/uploads/default/original/2X/6/6dcab99abc474af4f2755855b853f90622e9a7dd.png)

Per esempio qui l’algoritmo arriva al 2 tramite il 3, anche se sarebbe più corto arrivarci tramite l’1.

Ho pensato a 2 alternative:

1. Faccio lo stesso approccio però con dijkstra, così posso aumentare di 1 i pesi degli archi che portano a un nodo con una guardia.
2. Tengo questo approccio ma faccio ripartire un’altra BFS dalla fine, aggiustando tutte le distanze in base al vicino che ce l’ha più piccola.

Ho già provato l’approccio 2 e sembra non funzionare, quindi penso che proverò l’1.

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [6 Ottobre 2023, 7:56pm UTC](https://forum.olinfo.it/t/patrol2-30-100-bfs/8521/4 "2023-10-06T19:56:44Z")

</div>

L’approccio 1 funziona: basta calcolare la distanza temporale per raggiungere ogni nodo non visitato aggiungendo +1 rispetto al nodo di partenza e metterlo in coda.  
Se il nodo a cui si arriva può essere raggiunto da una guardia si attende incrementando la distanza del nodo di 1 e lo si rimette in coda.  
L’unico problema è come prevedere quando il nodo d’arrivo può essere raggiunto da una guardia. Basta considerare la distanza per raggiungere quel nodo con la ciclicità degli spostamenti  
delle guardie. Il risultato è la distanza temporale per raggiungere l’ultimo nodo.

---

<div class="post-metadata">

**Author:** ![TommasoTode](https://forum.olinfo.it/user_avatar/forum.olinfo.it/tommasotode/32/2896_2.png) [@TommasoTode](https://forum.olinfo.it/u/TommasoTode)\
**Post date:** [8 Ottobre 2023, 5:14pm UTC](https://forum.olinfo.it/t/patrol2-30-100-bfs/8521/5 "2023-10-08T17:14:37Z")

</div>

Grazie mille 😄 .  
Con il primo ha funzionato, ho fatto 100/100.