Football Foundation [3687]

Este es un problema de la ACM *, este problema lo resolví en enero del 2010 como requerimiento para un trabajo escolar.
* La ACM es una sociedad para la educación y ciencias computacionales, por sus siglas: Association for Computing Machinery http://www.acm.org/. Esta ACM organiza concursos de programación a nivel mundial (con sus respectivas eliminatorias regionales) y tiene una extensa coleccion de problemas a resolver programando, los puedes consultar aca: http://livearchive.onlinejudge.org/index.php
El problema:

Se supone que hay una Football Foundation (Fundación de Futbol), dicha fundación ha creado un sensor que describe el comportamiento del balón basandose en una distribución cuadriculada del campo de juego. En cada celda de la cuadrícula un sensor puede detectar hacía que punto cardinal se dirige el balón según su movimiento: N-norte, S-sur, E-este, W-oeste (West ya que la defición original está en Inglés).

Graficamente esto se lo representa así:





Puedes ver la definición original en inglés aca FOFO

Las flechas muestran el punto de entrada y curso que ha seguido el balón, entonces, lo que se pide es escribir un programa para saber en cuantos pasos ha salido el balón del campo, o si éste se queda dentro del campo en un ciclo repetitivo (como en la grid2 de la imagen), se considera un paso cada cambio de una celda a otra.

La entrada de los datos al programa será a traves de archivos de texto, cada archivo contendrá una o más jugadas, representadas en una matriz de caracteres de la siguiente forma:
3 6 5 NEESWE WWWESS SNWWWW

Donde la primer línea con tres enteros indica, numero de filas, numero de columnas y el numero de columna por el cual entra el balón desde el norte (siempre entra desde el norte). Las celdas de la matriz contendrán, cada una, una letra que indica la direccion del balón en caso de caer en esa celda. Para saber cuando es el final del archivo se encontrará una línea con tres ceros.

La salida del programa, para cada jugada (cada cuadricula de movimientos) se generará una línea de salida en la cual se describirá el comportamiento del balón, poniendo cuantos pasos ocurrieron para la salida del balón del campo, o si hubo un ciclo del balón dentro del campo, cuantos pasos antes del ciclo y el numero de pasos que abarca el ciclo.

Ejemplos: 10 step(s) to exit 3 step(s) before a loop of 8 step(s)

Donde la línea salida corresponde a la grid1 de la imagen y la segunda a la grid2

Solución:

Mi idea para la solución fue utilizar una lista enlazada, cada elemento de la lista es una coordenada (valores x, y) por donde el balón ha pasado, así en cada paso que el balón hago lo siguiente, revisar si la coordenada de la nueva posición del balón ya está en la lista, si es así significa que el camino se ciclo y se termina el análisis, si no es así se agrega la coordenada a la lista y se procesa la celda según su valor (N | S | E | W) para mover el balón a su siguiente paso, si el siguiente paso cae fuera de los limites significa que el balón ha salido y termina el análisis.

Para procesar los pasos del balón previamente se carga la matriz de la cuadrícula en una array de caracteres, este array nos dara los limites de acuerdo a sus indices. Al terminar el análisis solo hay que ver el numero de los elementos en la lista de coordenadas y ese es el numero de pasos dados por el balón, excepto en el caso de cuando el balón se cicla, en ese caso los pasos dados son hasta antes de la coordenada que se repite, y el resto de pasos son el tamaño del ciclo.
Código fuente de la solución completo:
import java.io.File;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.awt.Point;

public class Pro3687{

  private static ArrayList<Point> coordenadas;

  public static void main(String[] args){
    char[][] datos;
    BufferedReader lector;
    int temp;
    String grid;
    StringTokenizer descomp;
    int fila;
    char paso;
    int aux;
    if(args.length==0){
      System.out.println("Error! debe indicar como argumento el nombre archivo de entrada de datos");
    }
    else{
      try{
        lector=new BufferedReader(new FileReader(args[0]));
        do{
          grid=lector.readLine();
          descomp=new StringTokenizer(grid);
          datos=new char[Integer.parseInt(descomp.nextToken())][Integer.parseInt(descomp.nextToken())];
          temp=Integer.parseInt(descomp.nextToken())-1;
          if(temp>-1){
            for(int i=0;i<datos.length;i++){
              grid=lector.readLine();
              for(int j=0;j<grid.length();j++){
                datos[i][j]=grid.charAt(j);
              }
            }
            iniCamino();
            fila=0;
            do{
              paso=datos[fila][temp];
              aux=existeCoordenada(temp,fila);
              if(aux!=-1){
                System.out.println(""+aux+" step(s) before a loop of "+(numeroCoordenadas()-aux)+" step(s)");
                fila=-10;
              }
              else{
                agregaCoordenada(temp,fila);
                fila+=(paso=='N'?-1:(paso=='S'?1:0));
                temp+=(paso=='E'?1:(paso=='W'?-1:0));
              }
            }while(fila>=0&&fila<datos.length && temp>=0&&temp<datos[0].length);
            if(fila>-10){
              System.out.println(""+numeroCoordenadas()+" step(s) to exit");
            }
          }
        }while(datos.length>0);
      }
      catch(Exception exc){
        System.out.println("Error! ocurrio la excepcion: "+exc.getMessage());
      }
    }
  }

  public static void iniCamino(){
    coordenadas=new ArrayList<Point>();
  }

  public static void agregaCoordenada(int x, int y){
    Point temp=new Point(x,y);
    coordenadas.add(temp);
  }

  public static int existeCoordenada(int x, int y){
    Point temp;
    for(int i=0;i<coordenadas.size();i++){
      temp=coordenadas.get(i);
      if(temp.getX()==x && temp.getY()==y){
        return i;
      }
    }
    return -1;
  }

  public static int numeroCoordenadas(){
    return coordenadas.size();
  }
}

Comentarios

Entradas populares