Poj Solution 2064

```http://poj.org/problem?id=2064

//* @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鋞ts 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;
}
}
}
}
}

```
This entry was posted in poj. Bookmark the permalink.