Patrol2 30/100 BFS

Aiuto
1

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.

#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 :slight_smile: .

2

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.

1 Mi Piace
3

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
grafo763×763 27.1 KB

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.

4

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.

1 Mi Piace
5

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