the algorithms in my homework


2004-02-20 08:01:47 PM
jbuilder18
hello
1. A cost-map contains M*N cells, we have the cost rate for each individual cell.
2. The path is defined as a sequence of cells that connect to each other directly.
3. If two cells are in the same row or column, and there is no cell between them, these two cells are defined as directly connected.
4. The cost of a path is the summary of all the cellsĄŻ costs involved.
question:
you are required to find out a cheapest path from one specified cell to another.
i have designed several class architecture as follow,maybe they are not complete,but it is not important,what i more care about is:how can i implement the algrithm to find the cheapest path?,who can give me the code snippet about the algrithm to get the cheapest path?or where can i find it?
thank you!
**********************************************************************
public class Map{
int A;
int B;
public Cell getCell(int row, int col){
}
public Cell getStartCell(){
}
public Cell getTargetCell(){
}
}
A: is the row number of the map
B: is the column number of the map
getCell returns the Cell with row and column specified. The start index is 0.
getStartCell and GetTargetCell return the start and end cell of the problem.
public class Cell{
int row;
int col;
public int getCost(){
}
}
public class Trace{
public int getTraceLength(){}
public Cell getCell(int n){}
public int getCost(){}
}
getTraceLength returns how many cells are involved in this trace.
getCell returns the number n cell in this trace.
getCost returns the total cost of this trace.