首页 > 数据结构 > Hash表 > POJ 2064 Pipes [解题报告] Java
2013
11-10

POJ 2064 Pipes [解题报告] Java

Pipes

问题描述 :

The construction of office buildings has become a very standardized task. Pre-fabricated modules are combined according to the customer’s needs, shipped from a faraway factory, and assembled on the construction site. However, there are still some tasks that require careful planning, one example being the routing of pipes for the heating system.

A modern office building ismade up of squaremodules, one on each floor being a service module from which (among other things) hot water is pumped out to the other modules through the heating pipes. Each module (including the service module) will have heating pipes connecting it to exactly two of its two to four neighboring modules. Thus, the pipes have to run in a circuit, from the service module, visiting each module exactly once, before finally returning to the service module. Due to different properties of the modules, having pipes connecting a pair of adjacent modules comes at different costs. For example, some modules are separated by thick walls, increasing the cost of laying pipes. Your task is to, given a description of a floor of an office building, decide the cheapest way to route the heating pipes.

输入:

The first line of input contains a single integer, stating the number of floors to handle. Then follow n floor descriptions, each beginning on a new line with two integers, 2 <= r <= 10 and 2 <= c <= 10, defining the size of the floor – r-by-c modules. Beginning on the next line follows a floor description in ASCII format, in total 2r + 1 rows, each with 2c + 2 characters, including the final newline. All floors are perfectly rectangular, and will always have an even number of modules. All interior walls are represented by numeric characters, '0' to '9', indicating the cost of routing pipes through the wall (see sample input).

输出:

For each test case, output a single line with the cost of the cheapest route.

样例输入:

3
4 3
#######
# 2 3 #
#1#9#1#
# 2 3 #
#1#7#1#
# 5 3 #
#1#9#1#
# 2 3 #
#######
4 4
#########
# 2 3 3 #
#1#9#1#4#
# 2 3 6 #
#1#7#1#5#
# 5 3 1 #
#1#9#1#7#
# 2 3 0 #
#########
2 2
#####
# 1 #
#2#3#
# 4 #
#####

样例输出:

28
45
10

解题代码:

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

class Layer
{
  int cost;
  int frontier[];
  int frontierCode;
  
  Layer(int f[], int c)
  {
    cost = c;
  	frontier = new int[f.length];
	frontierCode = 0;
	    
	for (int i=0; i< frontier.length; i++)
      frontier[i] = f[i];
	
	for (int i=0; i< frontier.length; i++)
    {
      if ((frontier[i] != Main.NO_PIPE) && (frontier[i] !=
 Main.NEW_PIPE))
      {
        if (i < frontier[i])
          frontierCode += (1 << (2*i));
        else
          frontierCode += (2 << (2*i));
      }
    }
  }
  
  public int hashCode()
  {
    return frontierCode;
  }
  
  public String toString()
  {
    return "Layer " + frontierCode + " with cost " + cost;
  }
	
  public boolean equals(Object o)
  {
  	Layer l = (Layer) o;
	return l.frontierCode == frontierCode;
  }
}
	
public class Main
{
  static int MAX_SIZE = 10;
  static int MAX_TABLE_SIZE = 1024*1024;

  static int NO_PIPE = -2;
  static int NEW_PIPE = -1;

  static int INFINITE_COST = 1000000;

  static int lr_costs[][];
  static int ud_costs[][];

  static boolean connected;
  static int lower_row;

  static int nbr_cols;
  static int nbr_rows;

  static HashMap old_costs;
  static HashMap new_costs;

  public static void main(String argv[]) throws Exception
  {
    int n;
    char ch;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    lr_costs = new int[MAX_SIZE][MAX_SIZE];
    ud_costs = new int[MAX_SIZE][MAX_SIZE];
	
    n = Integer.parseInt(br.readLine());

	for (int i=0; i< n; i++)
    {
      StringTokenizer tok = new StringTokenizer(br.readLine(), " ");
      
      nbr_rows = Integer.parseInt(tok.nextToken());
      nbr_cols = Integer.parseInt(tok.nextToken());

      old_costs = new HashMap();
      new_costs = new HashMap();
	  
	  int fr[] = new int[nbr_cols];
	  for (int j=0; j< nbr_cols; j++)
		fr[j] = NO_PIPE;
	  Layer null_layer = new Layer(fr, 0);
    
      br.readLine();

      for (int row=0; row< nbr_rows; row++)
      {
        String str = br.readLine();

        for (int col=0; col< nbr_cols-1; col++)
        {
          ch = str.charAt(col*2+2);

          if ('0' <= ch && ch <= '9')
            lr_costs[row][col] = (int) (ch - '0');
          else
            throw(new Exception());
        }

        str = br.readLine();

        if (row < nbr_rows-1)
        {
          for (int col=0; col< nbr_cols; col++)
          {
            ch = str.charAt(2*col+1);

            if ('0' <= ch && ch <= '9')
              ud_costs[row][col] = (int) (ch - '0');
            else
              throw(new Exception());
          }
        }
      }

      // Init first lower layer
      int frontier[] = new int[nbr_cols];

      for (int j=0; j< nbr_cols; j++)
        frontier[j] = NO_PIPE;

      lower_row = -1;
      connected = false;
      extend_layer(frontier, 0, 0, NO_PIPE);

      for (lower_row=0; lower_row< nbr_rows-1; lower_row++)
      {
        old_costs = new_costs;
        new_costs = new HashMap();

        Iterator it = old_costs.values().iterator();
		while (it.hasNext())
		{
          Layer layer = (Layer) it.next();
		  extend_layer(layer.frontier, 0, layer.cost, NO_PIPE);
		}
      }
      
	  Layer layer = (Layer) new_costs.get(null_layer);
      System.out.println(layer.cost);
    }
  }

  static void extend_layer(int f[], int col, int cost, int from_left)
  {
    int frontier[] = new int[nbr_cols];

    for (int i=0; i< nbr_cols; i++)
      frontier[i] = f[i];

    if (col == nbr_cols)
    {
      if (from_left == NO_PIPE)
      {
	  	Layer layer = new Layer(frontier, cost);
 		Layer layer2 = (Layer) new_costs.get(layer);
		if (layer2 != null)
		{
		  if (cost < layer2.cost)
		    layer2.cost = cost;
		}
        else
		  new_costs.put(layer, layer);
      }
      else
        return;
    }
    else if (from_left == NO_PIPE)
    {
      if (frontier[col] == NO_PIPE)
      {
        // UR pipe
        frontier[col] = NEW_PIPE;  // REMOVE s��s senare
        extend_layer(frontier, col+1, cost, col);
      }
      else
      {
        cost += ud_costs[lower_row][col];

        // DU pipe
        frontier[col] = frontier[col];  // REMOVE
        extend_layer(frontier, col+1, cost, NO_PIPE);

        // DR pipe
        int tmp = frontier[col];
        frontier[col] = NO_PIPE;
        extend_layer(frontier, col+1, cost, tmp);
      }
    }
    else
    {
      cost += lr_costs[lower_row+1][col-1];
      
      if (frontier[col] == NO_PIPE)
      {
        // LR pipe
        frontier[col] = NO_PIPE;  // REMOVE
        extend_layer(frontier, col+1, cost, from_left);

        // LU pipe
        frontier[col] = from_left;
        frontier[from_left] = col;
        extend_layer(frontier, col+1, cost, NO_PIPE);
      }
      else
      {
        cost += ud_costs[lower_row][col];

        // DL pipe
        if (from_left != col)
        {
          frontier[from_left] = frontier[col];
          frontier[frontier[col]] = from_left;
          frontier[col] = NO_PIPE;
          extend_layer(frontier, col+1, cost, NO_PIPE);
        }
        else if ((lower_row+2 == nbr_rows) && !connected)
        {
          connected = true;
          frontier[col] = NO_PIPE;
          extend_layer(frontier, col+1, cost, NO_PIPE);
          connected = false;
        }
      }
    }
  }
}

  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }