Enunciado y ejemplos:
SE PIDE diseñar e implementar un algoritmo utilizando programación dinámica para resolver este problema de forma óptima.
PathsFinder.java
import static java.lang.Math.*;
/**
* Práctica programación dinámica - Encontrar todos los caminos posibles desde un punto A a otro punto B
* existiendo la posibilidad de barreras.
* @author EstebanMontesMorales
*/
public class PathsFinder {
private long[][] M;
private Point size;
private Point begin;
private Point end;
private Point[] barriers;
public PathsFinder(Point size, Point begin, Point end, Point[] barriers){
this.size = size;
this.begin = begin;
this.end = end;
this.barriers = barriers;
this.M = new long[this.size.x][this.size.y];
//Minimizing the matrix if its necessary:
if(checkIfBarriersAtBegin() == true) prepareSpecial();
if(isNecessaryMinimize() || barriers == null) minimize();
}
private void addBarriers(Point barrierCoord){
M[barrierCoord.x][barrierCoord.y] = -1;
}
private void minimize(){
Point a = new Point((size.x-begin.x),(size.y-begin.y));
Point b = new Point((size.x-end.x),(size.y-end.y));
int nrows = max(a.x, b.x) - min(a.x, b.x);
int ncols = max(a.y, b.y) - min(a.y, b.y);
this.M = new long[nrows+1][ncols+1];
prepareBoard();
if(barriers != null){
// new barriers positions
for(int i=0; i<barriers.length; i++){
barriers[i] = new Point((nrows-barriers[i].x), (ncols-barriers[i].y));
addBarriers(barriers[i]);
}
}
}
private void prepareBoard(){
for(int i=0; i<M[0].length; i++){
M[0][i] = 1;
}
for(int i=0; i<M.length; i++){
M[i][0] = 1;
}
}
private void prepareSpecial(){
for(int i=0; i<M[0].length; i++){
M[1][i] = 1;
}
}
public long calcNumOfPaths(){
//Not valid inputs:
//check if we're inside of the board
boolean predicate = begin.x >= size.x || begin.y >= size.y || end.x >= size.x || end.y >= size.y;
boolean predicate2 = begin.x < 0 || begin.y < 0 || end.x < 0 || end.y < 0;
//check that the end point is not before of the begin point or in the same coord
boolean predicate3 = end.y <= begin.y || (end.x == begin.x && end.y == begin.y);
if(predicate || predicate2 || predicate3) return -1;
for(int i=1; i<M.length; i++){
for(int j=1; j<M[i].length; j++){
if(M[i][j] == -1) M[i][j] = 0;
else M[i][j] = M[i-1][j] + M[i][j-1];//recurrence f
}
}
return M[M.length-1][M[0].length-1];
}
private boolean isNecessaryMinimize(){
return ((begin.x + 1) != size.x && (begin.y + 1) != size.y);
}
private boolean checkIfBarriersAtBegin(){
boolean flag = false;
if(barriers == null) return flag;
for(Point p: barriers){
if(p.x==0 || p.y==0) flag=true;
else flag=false;
}
return flag;
}
public void showM(){
for(int i=0; i<M.length; i++){
for(int j=0; j<M[0].length; j++){
System.out.print(""+M[i][j]+"\t");
}
System.out.println();
}
}
}public class Point {
protected int x;
protected int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
public class DataLoader {
private Point begin;
private Point end;
private Point size;
private ArrayList<Point> barriers = new ArrayList<Point>();
public PathsFinder loadData(String fPath) throws IOException{
BufferedReader br = new BufferedReader(new FileReader(fPath));
StringBuilder sb = new StringBuilder();
String line = br.readLine();
int counter = 0;
while (line != null) {
sb.append(line);
sb.append(System.lineSeparator());
line = br.readLine();
}
String everything = sb.toString();
br.close();
String[] splitted = everything.split("\n");
String[] s1 = splitted[0].split(",");
size = new Point(Integer.parseInt(s1[0].split("")[0]), Integer.parseInt(s1[1].split("")[0]));
if(!splitted[1].equals("\r")){
String[] s2 = splitted[1].split(";");
for(String i : s2){
String[] s3 = i.split(",");
barriers.add(new Point(Integer.parseInt(s3[0].split("")[0]), Integer.parseInt(s3[1].split("")[0])));
}
}else{
barriers = null;
}
String[] s4 = splitted[2].split(";");
String s5 = s4[0].split(",")[0].split("")[0];
String s6 = s4[0].split(",")[1].split("")[0];
String s7 = s4[1].split(",")[0].split("")[0];
String s8 = s4[1].split(",")[1].split("")[0];
begin = new Point(Integer.parseInt(s5), Integer.parseInt(s6));
end = new Point(Integer.parseInt(s7), Integer.parseInt(s8));
PathsFinder pf = null;
if(barriers != null){
Point[] barriersArray = new Point[barriers.size()];
for(int i=0; i<barriers.size(); i++)
barriersArray[i] = barriers.get(i);
pf = new PathsFinder(size, begin, end, barriersArray);
}else{
pf = new PathsFinder(size, begin, end, null);
}
return pf;
}
}import static org.junit.Assert.*;
import java.io.IOException;
import org.junit.Test;
public class DPTests {
@Test
public void caso1() {
DataLoader d = new DataLoader();
try {
System.out.println("##### CASO 1 #####");
PathsFinder caso1 = d.loadData("C:\\Users\\Esteban\\Documents\\casos\\caso1.txt");
assertEquals(2, caso1.calcNumOfPaths());
caso1.showM();
System.out.println("#################");
} catch (IOException e) {
e.printStackTrace();
}
}
@Test
public void caso2(){
DataLoader d = new DataLoader();
PathsFinder caso2;
try {
System.out.println("##### CASO 2 #####");
caso2 = d.loadData("C:\\Users\\Esteban\\Documents\\casos\\caso2.txt");
assertEquals(252, caso2.calcNumOfPaths());
caso2.showM();
System.out.println("#################");
System.out.println();
} catch (IOException e) {
e.printStackTrace();
}
}
@Test
public void caso3(){
DataLoader d = new DataLoader();
PathsFinder caso3;
try {
System.out.println("##### CASO 3 #####");
caso3 = d.loadData("C:\\Users\\Esteban\\Documents\\casos\\caso3.txt");
assertEquals(0, caso3.calcNumOfPaths());
caso3.showM();
System.out.println("#################");
System.out.println();
} catch (IOException e) {
e.printStackTrace();
}
}
@Test
public void caso4(){
System.out.println("##### CASO 4 #####");
PathsFinder pf = new PathsFinder(new Point(32, 36), new Point(31, 0), new Point(0, 35), null);
System.err.println("El número de caminos posibles es: " + pf.calcNumOfPaths());
pf.showM();
System.out.println();
System.out.println("#################");
}
@Test
public void caso5(){
DataLoader d = new DataLoader();
PathsFinder caso5;
try {
System.out.println("##### CASO 5 #####");
caso5 = d.loadData("C:\\Users\\Esteban\\Documents\\casos\\caso5.txt");
assertEquals(4, caso5.calcNumOfPaths());
caso5.showM();
System.out.println("#################");
System.out.println();
} catch (IOException e) {
e.printStackTrace();
}
}
@Test
public void caso6(){
DataLoader d = new DataLoader();
PathsFinder caso6;
try {
System.out.println("##### CASO 6 #####");
caso6 = d.loadData("C:\\Users\\Esteban\\Documents\\casos\\caso6.txt");
assertEquals(2, caso6.calcNumOfPaths());
caso6.showM();
System.out.println("#################");
System.out.println();
} catch (IOException e) {
e.printStackTrace();
}
}
@Test
public void caso7(){
DataLoader d = new DataLoader();
PathsFinder caso7;
try {
System.out.println("##### CASO 7 #####");
caso7 = d.loadData("C:\\Users\\Esteban\\Documents\\casos\\caso7.txt");
assertEquals(-1, caso7.calcNumOfPaths());
caso7.showM();
System.out.println("#################");
System.out.println();
} catch (IOException e) {
e.printStackTrace();
}
}
@Test
public void caso8(){
DataLoader d = new DataLoader();
PathsFinder caso7;
try {
System.out.println("##### CASO 8 #####");
caso7 = d.loadData("C:\\Users\\Esteban\\Documents\\casos\\caso8.txt");
assertEquals(-1, caso7.calcNumOfPaths());
caso7.showM();
System.out.println();
System.out.println("#################");
} catch (IOException e) {
e.printStackTrace();
}
}
@Test
public void caso9(){
DataLoader d = new DataLoader();
PathsFinder caso7;
try {
System.out.println("##### CASO 9 #####");
caso7 = d.loadData("C:\\Users\\Esteban\\Documents\\casos\\caso9.txt");
assertEquals(-1, caso7.calcNumOfPaths());
caso7.showM();
System.out.println("#################");
System.out.println();
} catch (IOException e) {
e.printStackTrace();
}
}
}
Formato de los casos de prueba (.txt):
