Skip to content

UVA Problem: 12101 (Prime Path )

October 5, 2011

Problem Statement:

Problem Explanation:

This is a simple BFS problem . There is nothing special to mention for this problem.

1.  First generate prime number upto  9999.

2.  Then just run BFS from the initial number. Like if the number is 1033 where else we can go

2.a  Changing the first digit we get 8 number (2-9)033, changing second digit we get 9 number 1(1-9)33 and so  on.  If   any of the number is prime then place it in queue and mark this as visited so that you don’t push it again.

3.  Push and Pop the numbers until you get the desired number. If number not found print “Impossible.” else print the distance.

Advertisements
No comments yet

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: