hi...
I've used BFS algorithm to solve 567 of UVA...
but it takes WA...
here's my solution in c++:
#include <iostream>
#include <queue>
#include <cstring>
#include <stdio.h>
using namespace std;
int mat[21][21];
int mark[21];
int tc = 0;
int n, m, t;
int a, b;
void bfs ()
{
queue <int> q;
q.push (a);
mark[a] = 0;
while (!q.empty())
{
int temp = q.front();
q.pop();
if (temp == b)
return;
for (int i = 1; i <= 20; i++)
if (mat[temp][i] == 1 && mark[i] == -1)
{
q.push (i);
mark[i] = mark[temp] + 1;
}
}
}
int main ()
{
//freopen ("input.in", "r", stdin);
while (!cin.eof())
{
tc++;
for (int i = 0; i < 21; i++)
memset (mat[i], 0, sizeof mat[i]);
for (int i = 1; i <= 19 && cin >> n; i++)
for (int j = 0; j < n && cin >> m; j++)
{
mat[i][m] = 1;
mat[m][i] = 1;
}
cin >> t;
cout << "Test Set #" << tc << endl;
for (int i = 0; i < t && cin >> a >> b; i++)
{
memset (mark, -1, sizeof mark);
bfs ();
printf ("%2d", a);
cout << " to ";
printf ("%2d", b);
cout << ": " << mark[b] << endl;
}
cout << endl;
}
return 0;
}
Is there anyone to help me?!
tnx
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
