UVA – 168 – Theseus and the Minotaur

  • Problem Statement : UVA – 168 – Theseus and the Minotaur
  • Type : Constrained DFS
  • Solution : actually this is a really dirty problem 😐 😐 not only in the input, but I took long time to understand it besides i watched a documentary on the Youtube about the legend as well 😀 typically here you will do a DFS but you have to take care of the following.
    • a node is marked as visited only when it has a candle so that happens whenever Theseus passes the Kth cave.
    • this is the most important point; the adjacent nodes should be traversed in the order given in the input.
#include<vector>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 300

const int N = 26;
int K;

int go(int M, int T, int step, vector<int> adj[MAX], bool candle[MAX]) {
	candle[M] = !((++step) % K);
	for (size_t v = 0; v < adj[M].size(); v++)
		if (!candle[adj[M][v]] && adj[M][v] != T) {
			if (candle[M]) cout << char(M) << " ";
			return go(adj[M][v], M, step, adj, candle);
		}
	cout << "/" << char(M) << endl;
	return 0;
}
int main() {
	string line;
	while (getline(cin, line) && line != "#") {
		bool vis[MAX];
		vector<int> adj[MAX];
		size_t s, t, i, ei = 0; int e[2];
		string tmp = "";
		for (i = 0; i < line.size(); i++) {
			if (line[i] == '.') break;
			if (line[i] == ':' || line[i] == ';') ei = line[i] == ':' ? 1 : 0;
			else {
				e[ei] = line[i];
				if (ei == 1) adj[e[0]].push_back(e[1]);
			}
		}
		{
			i++;
			while (line[i] == ' ') i++;  s = line[i++];
			while (line[i] == ' ') i++;  t = line[i++];
			while (line[i] == ' ') i++;  K = 0;
			while (i < line.size()) K = K * 10 + (line[i++] - '0');
		}
		memset(vis, 0, sizeof(vis));
		go(s, t, 0, adj, vis);
	}
	return false;
}
Extra Test cases :-

A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 1
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 6
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 7
A:B;B:A. B A 3
A:B;B:C;C:A. B A 6
C:A;A:B. A C 999999999
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1
A:DBC. A B 20
A:DBC. A B 1
A:BC:A A B 1
#

Output :

D F G /E
A B C D G E F /H
C D /B
A B D /C
/B
A /C
/B
D F G /E
A B D G E F /H
/D
A /D
/A
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: