168 - Theseus and the Minotaur

[pineapple]

I have read many threads about this problem.But I still can't get Accepted.
Who can help me?Please give me some cases I can't handle or point out my mistake.Thanks very much.

The following is my code:

Code: Select all

Accepted!

[rickyliu]

Try this:

Code: Select all

A:DBC. A B 20
#

Your answer is:

Code: Select all

/C

The correct answer should be:

Code: Select all

/D

[pineapple]

Thank you very much!
Your test case is very helpful to me.
I changed my code a little and get AC!
then I will delete my code above.
Thanks again.

[shamsacm]

Try This
Input

Code: Select all

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:

Code: Select all

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

[vo_minhdat2007]

Try this:

Code: Select all

A:DBC. A B 20
#

Your answer is:

Code: Select all

/C

The correct answer should be:

Code: Select all

/D

Hello, please explains why the answer is /D? If I understand the problem correctly, the graph should be like this:



And

where in this case the Minotaur checks the exits from a cavern in alphabetical order

So Minotaur should go to C (because C < D) and be trapped there immediately?

[brianfry713]

Read the problem description again. It was alphabetical just for the sample case. "The description of a labyrinth will identify each cavern by an upper case character and will list the caverns reachable from that cavern in the order that the Minotaur will attempt them"

In the input

Code: Select all

A:DBC. A B 20
#

The Minotaur will attempt to go from A first to D, then B, then C.

[vo_minhdat2007]

Read the problem description again. It was alphabetical just for the sample case. "The description of a labyrinth will identify each cavern by an upper case character and will list the caverns reachable from that cavern in the order that the Minotaur will attempt them"

In the input

Code: Select all

A:DBC. A B 20
#

The Minotaur will attempt to go from A first to D, then B, then C.

Thank you, I got it!

[vo_minhdat2007]

I wonder which test case that cause the TLE. Here is my code, please give me some big case and I will try to improve it.

(My program return results correctly for problems at this topic: http://online-judge.uva.es/board/viewto ... =1&t=14236)

Code: Select all

import java.util.ArrayList;
import java.util.Scanner;


public class Main {

	//===============================================//
	// Inner Classes
	//===============================================//
	
	public class ArrayListInteger {
		public ArrayList<Integer> value = new ArrayList<Integer>();
	}
	
	//===============================================//
	// Variables
	//===============================================//
	
	private static ArrayListInteger[] mAdjacentVertexes;
	private static boolean[] mVertexDisabled;
	private static int mFinalVertex = 0;
	private static int mThesusVertex = 0;
	private static int mMinotaurVertex = 0;
	private static int mK = 0;
	
	//===============================================//
	// Public Methods
	//===============================================//
	
	public static void parseInput(String pRawData) {
		String[] periodDelimiter = pRawData.split("\\.");
		
		String[] passages = periodDelimiter[0].split(";");
		for (int i = 0; i < passages.length; i++) {
			int startVertex = passages[i].charAt(0) - 'A';
			if (startVertex > mFinalVertex) mFinalVertex = startVertex;
			
			for (int j = 2; j < passages[i].length(); j++) {
				int endVertex = passages[i].charAt(j) - 'A';
				if (endVertex > mFinalVertex) mFinalVertex = endVertex;
				
				mAdjacentVertexes[startVertex].value.add(endVertex);
			}
		}
		mFinalVertex++;
		
		String initData[] = periodDelimiter[1].trim().split(" ");
		mMinotaurVertex = initData[0].charAt(0) - 'A';
		mThesusVertex = initData[1].charAt(0) - 'A';
		mK = Integer.parseInt(initData[2]);
	}

	public static String traverse() {
		String result = "";
		
		int mTravelCount = 0;
		int nextVertex = -1;
		do {
			nextVertex = -1;
			
			for (int i = 0; i < mAdjacentVertexes[mMinotaurVertex].value.size(); i++) {
				int currentVertex = mAdjacentVertexes[mMinotaurVertex].value.get(i);
				if (mVertexDisabled[currentVertex] || currentVertex == mThesusVertex) continue;
				nextVertex = currentVertex;
				break;
			}
			
			if (nextVertex != -1) {
				mTravelCount++;
				if (mAdjacentVertexes[mThesusVertex].value.indexOf(mMinotaurVertex) != -1)
					mThesusVertex = mMinotaurVertex;
				mMinotaurVertex = nextVertex;
				
				if (mTravelCount == mK) {
					// Print result
					result += (char)(mThesusVertex + 'A') + " ";
					
					// Clear this vertex
					mVertexDisabled[mThesusVertex] = true;
					
					mTravelCount = 0;
				}
			}
		} while (nextVertex != -1);
		result += "/" + (char)(mMinotaurVertex + 'A');
		
		return result;
	}
	
	public static void main(String[] args) {
		String result = "";
		Scanner scanner = new Scanner(System.in);
		
		// Initialize
		mAdjacentVertexes = new ArrayListInteger[26];
		Main obj = new Main();
		for (int i = 0; i < 26; i++) {
			mAdjacentVertexes[i] = obj.new ArrayListInteger();
		}
		mVertexDisabled = new boolean[26];
		
		String currentInput = scanner.nextLine();
		while (!currentInput.equals("#")) {
			
			// Reset value
			for (int i = 0; i < 26; i++) {
				mAdjacentVertexes[i].value.clear();
				mVertexDisabled[i] = false;
			}
			mFinalVertex = 0;
			
			// Input
			parseInput(currentInput);
			
			// Traverse
			result += traverse() + "\n";
			
			// Next line
			currentInput = scanner.nextLine();
		}
		
		System.out.print(result);
	}
	
}

Thank you.

[brianfry713]

Input:

Code: Select all

B:A;A:B. A C 999999999
#

AC output:

Code: Select all

/B

[vo_minhdat2007]

Thank you brianfry713,

Maybe I'm having too much misunderstanding about this problem. In that test case,

If a cavern has no exit it may or may not be in the input.

So C doesn't have any connection with A and B, so Theseus cannot chase the Minotaur? Then if I try comment out this line:

Code: Select all

if (mAdjacentVertexes[mThesusVertex].value.indexOf(mMinotaurVertex) != -1)

So Theseus can freely chase after Minotaur, the program works well with that test case, but I still get another TLE.

[brianfry713]

Yeah that test case I posted is probably invalid but the line you commented out is not needed to get AC and will slow down your code.
I optimized your code and got AC in 1.392 sec. JAVA is always going to be slow, so make sure you are coding efficiently and sometimes you should try C/C++ instead. Use BufferedReader and BufferedWriter for I/O. mFinalVertex is not needed so get rid of it. Building the entire output into a string is slower than printing it immediately onto a BufferedWriter.

[Sawon90]

For every case above, my code gives correct output. But why I am getting wrong answer???? Please someone help me. Thanks in advance. Here is my code....

Code: Select all

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
char st[250];
long i,n,ts,mt,k,vis[35],c,sz;
vector<long>vc[35],op;
bool fg;
int main()
{
	while(gets(st) && strcmp(st,"#"))
	{
		for(i=0;i<30;i++)
		{
			vc[i].clear();
			vis[i]=0;
		}
		for(i=0;st[i];i++)
		{
			if(st[i]>='A' && st[i]<='Z')
			{
				n=st[i]-65;
				i+=2;
				while(st[i]>='A' && st[i]<='Z')
				{
					vc[n].push_back(st[i]-65);
					i++;
				}
			}
			if(st[i]=='.')
			{
				mt=st[i+2]-65;
				ts=st[i+4]-65;
				k=st[i+6]-'0';
				break;
			}
		}
		c=0;
		while(1)
		{
			fg=0;
			sz=vc[mt].size();
			for(i=0;i<sz;i++)
			{
				n=vc[mt][i];
				if(vis[n] || n==ts)
					continue;
				else
				{
					c++;
					fg=1;
					ts=mt;
					mt=n;
					if(c==k)
					{
						op.push_back(ts);
						vis[ts]=1;
						c=0;
					}
					break;
				}
			}
			if(fg==0)
				break;
		}
		sz=op.size();
		for(i=0;i<sz;i++)
			printf("%c ",op[i]+65);
		printf("%c%c\n",47,mt+65);
		op.clear();
	}
	return 0;
}

[Sawon90]

Oh God, Please someone help me, Please someone tell me what will be the output of the following cases...

Code: Select all

A:BCD;B:AD;C:AD;D:B. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG. A C 3

Please someone help me.

[Sawon90]

Please help me to find why I am getting wrong answer in this problem. Here is my code....

Code: Select all

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
char st[250];
long i,n,ts,mt,k,vis[35],c,sz;
vector<long>vc[35],op;
bool fg;
int main()
{
	while(gets(st) && strcmp(st,"#"))
	{
		for(i=0;i<30;i++)
		{
			vc[i].clear();
			vis[i]=0;
		}
		for(i=0;st[i];i++)
		{
			if(st[i]>='A' && st[i]<='Z')
			{
				n=st[i]-65;
				i+=2;
				while(st[i]>='A' && st[i]<='Z')
				{
					vc[n].push_back(st[i]-65);
					i++;
				}
			}
			if(st[i]=='.')
			{
				mt=st[i+2]-65;
				ts=st[i+4]-65;
				k=st[i+6]-'0';
				break;
			}
		}
		c=0;
		while(1)
		{
			fg=0;
			sz=vc[mt].size();
			for(i=0;i<sz;i++)
			{
				n=vc[mt][i];
				if(vis[n] || n==ts)
					continue;
				else
				{
					c++;
					fg=1;
					ts=mt;
					mt=n;
					if(c==k)
					{
						op.push_back(ts);
						vis[ts]=1;
						c=0;
					}
					break;
				}
			}
			if(fg==0)
				break;
		}
		sz=op.size();
		for(i=0;i<sz;i++)
			printf("%c ",op[i]+65);
		printf("%c%c\n",47,mt+65);
		op.clear();
	}
	return 0;
}

Please help me.. What will be the output for these case.....

Code: Select all

A:BCD;B:AD;C:AD;D:B. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG. A C 3

Thanks in advance....

[brianfry713]

http://www.uvatoolkit.com/problemssolve.php