Lets say there is a river that is η meters wide. At every meter from the starting shore, there may or may not be a stone enough for frog to sit. Now a frog needs to cross the river. However the frog has the limitation that if it has just jumped x meters, then it can take next jump only of size x-1, x or x+1 meters. First jump can be of only 1 meter when starting from shore.
Assume frog can see all stone from this shore to opposite shore. Can frog determine whether it can make it to the other end or not.
Assume frog can see all stone from this shore to opposite shore. Can frog determine whether it can make it to the other end or not.
Following is implementation of above problem in c language.
Please write comments if you find anything wrong or you want to add something more related to this topic.
2 comments:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class test1 {
static int path_array[] = {1,1,1,1,0,0,1,0,1,1};
static int path_length;
static ArrayList path_list = new ArrayList();
static class info{
int speed;
int index;
int len;
public info(int s, int i, int l) {
speed = s;
index = i;
len = l;
}
}
public static void print(info i){
System.out.println("index=" + i.index + ", speed=" + i.speed + ", len=" + i.len);
}
public static boolean check(Queue queue){
info ori_info;
while(!queue.isEmpty()){
ori_info = queue.poll();
if(ori_info.len == path_length) return true;
info new_info = new info(ori_info.speed, ori_info.index+1, ori_info.len);
int edge = 0;
while(new_info.index < path_list.size()){
edge += path_list.get(new_info.index);
if(new_info.speed - 1 == edge){
queue.offer(new info(
new_info.speed - 1, new_info.index, new_info.len + edge));
}
if(new_info.speed == edge){
queue.offer(new info(
new_info.speed, new_info.index, new_info.len + edge));
}
if(new_info.speed + 1 == edge){
queue.offer(new info(
new_info.speed + 1, new_info.index, new_info.len + edge));
}
new_info.index++;
}
}
return false;
}
public static void main(String[] args) {
int edge = 1;
for(int p : path_array){
if(p == 0) edge++;
else{
path_length += edge;
path_list.add(edge);
edge = 1;
}
}
Queue queue = new LinkedList();
queue.add(new info(1, 0, 1));
System.out.println(check(queue));
}
}
Post a Comment
Write your comment here.