首页 > 专题系列 > Java解POJ > POJ 3653 Here We Go(relians) Again [解题报告] Java
2013
11-13

POJ 3653 Here We Go(relians) Again [解题报告] Java

Here We Go(relians) Again

问题描述 :

The Gorelians are a warlike race that travel the universe conquering new worlds as a form of recreation. Given their violent, fun-loving nature, keeping their leaders alive is of serious concern. Part of the Gorelian security plan involves changing the traffic patterns of their cities on a daily basis, and routing all Gorelian Government Officials to the Government Building by the fastest possible route.

Fortunately for the Gorelian Minister of Traffic (that would be you), all Gorelian cities are laid out as a rectangular grid of blocks, where each block is a square measuring 2520 rels per side (a rel is the Gorelian Official Unit of Distance). The speed limit between two adjacent intersections is always constant, and may range from 1 to 9 rels per blip (a blip, of course, being the Gorelian Official Unit of Time). Since Gorelians have outlawed decimal numbers as unholy (hey, if you’re the dominant force in the known universe, you can outlaw whatever you want), speed limits are always integer values. This explains why Gorelian blocks are precisely 2520 rels in length: 2520 is the least common multiple of the integers 1 through 9. Thus, the time required to travel between two adjacent intersections is always an integer number of blips.

In all Gorelian cities, Government Housing is always at the northwest corner of the city, while the Government Building is always at the southeast corner. Streets between intersections might be one-way or two-way, or possibly even closed for repair (all this tinkering with traffic patterns causes a lot of accidents). Your job, given the details of speed limits, street directions, and street closures for a Gorelian city, is to determine the fastest route from Government Housing to the Government Building. (It is possible, due to street directions and closures, that no route exists, in which case a Gorelian Official Temporary Holiday is declared, and the Gorelian Officials take the day off.)

Gorelian city

The picture above shows a Gorelian City marked with speed limits, one way streets, and one closed street. It is assumed that streets are always traveled at the exact posted speed limit, and that turning a corner takes zero time. Under these conditions, you should be able to determine that the fastest route from Government Housing to the Government Building in this city is 1715 blips. And if the next day, the only change is that the closed road is opened to two way traffic at 9 rels per blip, the fastest route becomes 1295 blips. On the other hand, suppose the three one-way streets are switched from southbound to northbound (with the closed road remaining closed). In that case, no route would be possible and the day would be declared a holiday.

输入:

The input consists of a set of cities for which you must find a fastest route if one exists. The first line of an input case contains two integers, which are the vertical and horizontal number of city blocks, respectively. The smallest city is a single block, or 1 by 1, and the largest city is 20 by 20 blocks. The remainder of the input specifies speed limits and traffic directions for streets between intersections, one row of street segments at a time. The first line of the input (after the dimensions line) contains the data for the northernmost east-west street segments. The next line contains the data for the northernmost row of north-south street segments. Then the next row of east-west streets, then north-south streets, and so on, until the southernmost row of east-west streets. Speed limits and directions of travel are specified in order from west to east, and each consists of an integer from 0 to 9 indicating speed limit, and a symbol indicating which direction traffic may flow. A zero speed limit means the road is closed. All digits and symbols are delimited by a single space. For east-west streets, the symbol will be an asterisk ‘*’ which indicates travel is allowed in both directions, a less-than symbol ‘<’ which indicates travel is allowed only in an east-to-west direction, or a greater-than symbol ‘>’ which indicates travel is allowed only in a west-to-east direction. For north-south streets, an asterisk again indicates travel is allowed in either direction, a lowercase “vee” character ‘v’ indicates travel is allowed only in a north-to-south directions, and a caret symbol ‘^’ indicates travel is allowed only in a south-to-north direction. A zero speed, indicating a closed road, is always followed by an asterisk. Input cities continue in this manner until a value of zero is specified for both the vertical and horizontal dimensions.

输出:

For each input scenario, output a line specifying the integer number of blips of the shortest route, a space, and then the word “blips”. For scenarios which have no route, output a line with the word “Holiday”.

样例输入:

2 2
9 * 9 *
6 v 0 * 8 v
3 * 7 *
3 * 6 v 3 *
4 * 8 *
2 2
9 * 9 *
6 v 9 * 8 v
3 * 7 *
3 * 6 v 3 *
4 * 8 *
2 2
9 * 9 *
6 ^ 0 * 8 ^
3 * 7 *
3 * 6 ^ 3 *
4 * 8 *
0 0

样例输出:

1715 blips
1295 blips
Holiday

解题代码:

//* @author: SmilingWang
import java.util.*;
import java.io.*;

public class Main {
 static final int INF = 100000000;
 public static void main(String[] args){
   Scanner in = new Scanner(new BufferedInputStream(System.in));
   int x = in.nextInt();
   int y = in.nextInt();
   while(x != 0 || y != 0){
	int w[][] = new int[(x+1)*(y+1)+1][(x+1)*(y+1)+1];
	//int num = 1;
	int row = 1;
	for(int i = 1; i <= 2*x+1; i++){
        if(i % 2 == 1){
	   //num = (row-1)*(y+1) + 1;
	   for(int j = 1; j <= y; j++){
		int tm = in.nextInt();
		String tms = in.next();
						
		if(tms.equals("*")){
		  w[(row-1)*(y+1)+j][(row-1)*(y+1)+j+1] = tm;
		  w[(row-1)*(y+1)+j + 1][(row-1)*(y+1)+j] = tm;
		}
		else if(tms.equals("< ")){
		  w[(row-1)*(y+1)+j + 1][(row-1)*(y+1)+j] = tm;
		}
		else if(tms.equals(">")){
		  w[(row-1)*(y+1)+j][(row-1)*(y+1)+j+1] = tm;
		}
	    }
	    row++;
	  }
	 else{
	   for(int j = 1; j <= y + 1; j++){
	    int tm = in.nextInt();
	    String tms = in.next();
			
          if(tms.equals("*")){
		w[(row-2)*(y+1) + j][(row-1)*(y+1) + j] = tm;
		w[(row-1)*(y+1) + j][(row-2)*(y+1) + j] = tm;
	   }
	  else if(tms.equals("^")){
		w[(row-1)*(y+1) + j][(row-2)*(y+1) + j] = tm;
	  }
	  else if(tms.equals("v")){
		w[(row-2)*(y+1) + j][(row-1)*(y+1) + j] = tm;
	  }
	}
    }
   }
  for(int p = 1; p <= (x+1)*(y+1); p++){
   for(int q = 1; q <= (x+1)*(y+1); q++){
	if(p == q){
         continue;
	}
	if(w[p][q] > 0){
	  w[p][q] = 2520/w[p][q];
	  continue;
	}
	w[p][q] = INF;
     }
   }
			
   dijkstra(w, (x+1)*(y+1));			
   x = in.nextInt();
   y = in.nextInt();
 }
}

public static void dijkstra(int w[][], int v){
  int i, vnear = 0;
  int touch[] = new int[v+1];
  int length[] = new int[v+1];
  boolean y[] = new boolean[v+1];
  int map[] = new int[v+1];
  PriorityQueue< Item> heap = new PriorityQueue< Item>(v, new ItemCompare());
		
  for(i = 2; i <= v; i++){
   length[i] = w[1][i];
   if(length[i] < INF){
	heap.add(new Item(1, i, w[1][i]));
   }
  }
  //System.out.println(heap);
  while(!heap.isEmpty()){
	Item temp = heap.remove();
			
	for(i = 1; i <= v; i++){
        if(i == temp.sv){
		continue;
	  }
	  else if(w[temp.ev][i] == INF){
		continue;
	  }
	  if(length[temp.ev] + w[temp.ev][i] < length[i]){
	   length[i] = length[temp.ev] + w[temp.ev][i];
	   heap.add(new Item(temp.ev, i, length[i]));
	  }
	 }
	}
	if(length[v] < INF){
	  System.out.println(length[v] + " blips");
	}
	else{
	  System.out.println("Holiday");
	}
    }
	
}

class Item{
 int sv;
 int ev;
 int w;
	
 Item(int sv, int ev, int w){
    this.sv = sv;
    this.ev = ev;
    this.w  = w;
   }
	
  public String toString(){
	return this.sv + " " + this.ev +" " + this.w;
  }
}

class ItemCompare implements Comparator< Item>{
	public int compare(Item i1, Item i2){
		return (i1.w - i2.w);
	}
}

  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?