Algoritmo de Busqueda de Cuadrados en Matriz aleatoria de unos

Descargar Codigo Fuente
Hoy les traigo un pequeño ejercicio, el cual consiste en hallar cuadrados en una matriz aleatoria de unos y ceros, en dicha matriz existen dos tipos de cuadrados los de ángulo 0° y ángulo 45°, siendo breves les traigo un ejemplo:

Matriz de 6 X 6
    0   1   2   3   4   5
0  0   0   1   0   1   1
1  0   1   0   1   1   1
2  1   0   1   0   1   0
3  0   1   0   1   0   0
4  0   0   1   0   0   0
5  1   0   0   1   0   0

En este caso las coordenadas estan determinadas en filas y columnas, en el ejercicio piden encontrar los puntos que forman los cuadrados, citemos un ejemplo:

El cuadrado de color verde esta formado por los siguientes puntos
(4,0);(4,1);(5,0);(5,1)  si esto lo comparamos con un plano cartesiano la variable "X" o abcisa seria el valor de la columna y la variable "Y" o Ordenada sería el valor de fila.

IDE Usado Netbeans.
Lenguaje de Programación: JAVA
IN/OUTPUT DATA : Consola

Estructura del Proyecto:

Beans:
package com.square.bean;

import java.util.ArrayList;

/**
 *
 * @author Administrador
 */
public class Cuadrado {
    ArrayList<Punto> puntos=new ArrayList();
    int angulo;
    public int getAngulo() {
        return angulo;
    }
    public ArrayList<Punto> getPuntos() {
        return puntos;
    }
    public void setAngulo(int angulo) {
        this.angulo = angulo;
    }
    public void setPuntos(ArrayList<Punto> puntos) {
        this.puntos = puntos;
    }
}
***********************************************************************************

package com.square.bean;

/**
 *
 * @author Administrador
 */
public class Matriz {
    private int filas;
    private int columnas;
    private Value[][] arreglo;   
    public Matriz(int row,int column,Value[][]matrix){
        filas=row;
        columnas=column;
        arreglo=matrix;
    }
    public Value[][] getArreglo() {
        return arreglo;
    }
    public void setArreglo(Value[][] arreglo) {
        this.arreglo = arreglo;
    }
    public int getColumnas() {
        return columnas;
    }
    public void setColumnas(int columnas) {
        this.columnas = columnas;
    }
    public int getFilas() {
        return filas;
    }
    public void setFilas(int filas) {
        this.filas = filas;
    }   
}

***********************************************************************************

package com.square.bean;
/**
 *
 * @author Administrador
 */
public class Punto {
    int fila;
    int columna;
    public Punto(int x,int y){
        fila=x;
        columna=y;
    }
    public int getColumna() {
        return columna;
    }
    public void setColumna(int columna) {
        this.columna = columna;
    }
    public int getFila() {
        return fila;
    }
    public void setFila(int fila) {
        this.fila = fila;
    }               
}

***********************************************************************************

package com.square.bean;
/**
 *
 * @author Administrador
 */
public class Value {
    private String valor;
    private Punto point;   
    public Value(String val,Punto p){
        valor=val;
        point=p;
    }   
    public Punto getPoint() {
        return point;
    }
    public void setPoint(Punto point) {
        this.point = point;
    }
    public String getValor() {
        return valor;
    }
    public void setValor(String valor) {
        this.valor = valor;
    }   
}

***********************************************************************************
Dao:

package com.square.dao;

import com.square.bean.Matriz;
import com.square.bean.Punto;
import com.square.bean.Value;
import java.util.ArrayList;
import java.util.Random;
/**
 *
 * @author Administrador
 */
public class DaoMatriz {   
    public static Matriz generarMatriz(int filas,int columnas){
        Value[][] matriz=new Value[filas][columnas];
        double aux;
        int valor;
        Random rnd = new Random();;
        for(int i=0;i<filas;i++){
            for(int j=0;j<columnas;j++){               
                aux=rnd.nextDouble();               
                valor=(int)Math.round(aux);
                Punto p=new Punto(i,j);
                Value val=new Value(String.valueOf(valor),p);
                matriz[i][j]=val;
            }
        }
        Matriz matrix=new Matriz(filas,columnas,matriz);
        return matrix;
    }   
    public static void paintMatriz(Matriz matrix){          
        for(int i=0;i<matrix.getFilas();i++){                                                 
            for(int j=0;j<matrix.getColumnas();j++){                               
                System.out.print(" "+matrix.getArreglo()[i][j].getValor()+" ");               
            }
            System.out.print("\n");
        }
    }   
    public static ArrayList<Value> paintMatrizUnos(Matriz matrix){  
        ArrayList<Value> listOne=new ArrayList<Value>();
        for(int i=0;i<matrix.getFilas();i++){                                                 
            for(int j=0;j<matrix.getColumnas();j++){                               
                if(matrix.getArreglo()[i][j].getValor().equals("0")){
                    matrix.getArreglo()[i][j].setValor(".");
                }else if(matrix.getArreglo()[i][j].getValor().equals("1")){
                    listOne.add(matrix.getArreglo()[i][j]);               
                }
                   
                System.out.print(" "+matrix.getArreglo()[i][j].getValor()+" ");               
            }
            System.out.print("\n");
        }
        return listOne;
    }                       
}

***********************************************************************************

Logic:

package com.square.Logic;

import com.square.bean.Cuadrado;
import com.square.bean.Matriz;
import com.square.bean.Punto;
import com.square.bean.Value;
import java.util.ArrayList;
import java.util.Iterator;

/**
 *
 * @author Administrador
 */
public class AlgoBusca {
    //ALGORTIMO 1
    public static ArrayList<Cuadrado> buscarCuadradosAngulo0(Matriz matrix, ArrayList<Value> unos) {
        ArrayList<Cuadrado> cuadrados=new ArrayList<Cuadrado>();
        Iterator i = unos.iterator();
        Value val;
        int maxlado = 0;
        int contador;       
        if (matrix.getColumnas() > matrix.getFilas()) {
            maxlado = matrix.getColumnas();
        } else {
            maxlado = matrix.getFilas();
        }
        boolean valpunto=false;
        while (i.hasNext()) {
            val=(Value)i.next();
            //Moviendose a la Derecha   
            contador = 2;
            valpunto=false;
            int fila;
            int columna;
            while (contador <= maxlado-val.getPoint().getColumna()) {
                try{
                fila=val.getPoint().getFila();
                columna=val.getPoint().getColumna();
                Cuadrado cua=new Cuadrado();
                //derecha               
                for(int j=1;j<contador;j++){                   
                    if(!matrix.getArreglo()[fila][columna+j].getValor().equals("1")){                       
                        valpunto=false;
                        break;
                    }else{
                        cua.getPuntos().add(matrix.getArreglo()[fila][columna+j].getPoint());
                        valpunto=true;
                    }
                }
                if(valpunto){
                    //abajo
for(int j=1;j<contador;j++){
                    if(!matrix.getArreglo()[fila+j][columna+contador-1].getValor().equals("1")){                   
                        valpunto=false;
                        break;
                    }else{
                        cua.getPuntos().add(matrix.getArreglo()[fila+j][columna+contador-1].getPoint());
                        valpunto=true;
                    }
                }   
                }else{
                    break;
                }
               
                if(valpunto){
                    //izquierda
                for(int j=1;j<contador;j++){
                    if(!matrix.getArreglo()[fila+contador-1][columna+contador-1-j].getValor().equals("1")){
                        valpunto=false;
                        break;
                    }else{
                        cua.getPuntos().add(matrix.getArreglo()[fila+contador-1][columna+contador-1-j].getPoint());
                        valpunto=true;
                    }
                }   
                }else{
                    break;
                }
               
                if(valpunto){
                    //arriba
                for(int j=1;j<contador;j++){
                    if(!matrix.getArreglo()[fila+contador-1-j][columna].getValor().equals("1")){
                        valpunto=false;
                        break;
                    }else{
                        cua.getPuntos().add(matrix.getArreglo()[fila+contador-1-j][columna].getPoint());
                        valpunto=true;
                    }
                }   
                }else{
                    break;
                }
                if(valpunto){
                 cua.setAngulo(0);
                cuadrados.add(cua);  
                }               
                contador=contador+1;
                }catch(Exception ex){
                contador=contador+1;
                }
            }
        }
        return cuadrados;
    }
    //ALGORTIMO 2
    public static ArrayList<Cuadrado> buscarCuadradosAngulo45(Matriz matrix, ArrayList<Value> unos) {
        ArrayList<Cuadrado> cuadrados=new ArrayList<Cuadrado>();
        Iterator i = unos.iterator();
        Value val;
        int maxlado = 0;
        int contador;       
        if (matrix.getColumnas() > matrix.getFilas()) {
            maxlado = matrix.getColumnas();
        } else {
            maxlado = matrix.getFilas();
        }
        boolean valpunto=false;
        while (i.hasNext()) {
            val=(Value)i.next();
            //Moviendose a la Derecha   
            contador = 2;
            valpunto=false;
            int fila;
            int columna;
            int auxfila=0;
            int auxcolum=0;
            while (contador <= maxlado-val.getPoint().getColumna()) {
                try{
                fila=val.getPoint().getFila();
                columna=val.getPoint().getColumna();
                Cuadrado cua=new Cuadrado();
               
                //NE              
                for(int j=1;j<contador;j++){                   
                    if(!matrix.getArreglo()[fila-j][columna+j].getValor().equals("1")){                       
                        valpunto=false;
                        break;
                    }else{
                        cua.getPuntos().add(matrix.getArreglo()[fila-j][columna+j].getPoint());
                        valpunto=true;
                        auxfila=fila-j;
                        auxcolum=columna+j;
                    }
                }
                if(valpunto){
                    //SE
                    fila=auxfila;
                    columna=auxcolum;
                for(int j=1;j<contador;j++){
                    if(!matrix.getArreglo()[fila+j][columna+j].getValor().equals("1")){                   
                        valpunto=false;
                        break;
                    }else{
                        cua.getPuntos().add(matrix.getArreglo()[fila+j][columna+j].getPoint());
                        valpunto=true;
                        auxfila=fila+j;
                        auxcolum=columna+j;
                    }
                }   
                }else{
                    break;
                }
               
                if(valpunto){
                    //SO
                    fila=auxfila;
                    columna=auxcolum;
                for(int j=1;j<contador;j++){
                    if(!matrix.getArreglo()[fila+j][columna-j].getValor().equals("1")){
                        valpunto=false;
                        break;
                    }else{
                        cua.getPuntos().add(matrix.getArreglo()[fila+j][columna-j].getPoint());
                        valpunto=true;
                        auxfila=fila+j;
                        auxcolum=columna-j;
                    }
                }   
                }else{
                    break;
                }
               
                if(valpunto){
                    //NO
                    fila=auxfila;
                    columna=auxcolum;
                for(int j=1;j<contador;j++){
                    if(!matrix.getArreglo()[fila-j][columna-j].getValor().equals("1")){
                        valpunto=false;
                        break;
                    }else{
                        cua.getPuntos().add(matrix.getArreglo()[fila-j][columna-j].getPoint());
                        valpunto=true;
                        auxfila=fila-j;
                        auxcolum=columna-j;
                    }
                }   
                }else{
                    break;
                }
                if(valpunto){
                 cua.setAngulo(45);
                cuadrados.add(cua);  
                }               
                contador=contador+1;
                }catch(Exception ex){
                contador=contador+1;
                }
            }
        }
        return cuadrados;
    }
   
    public static void imprimirCuadrados(ArrayList<Cuadrado> param){
        Iterator i=param.iterator();
        Iterator j;
        System.out.println("Imprimiendo Cuadrados");
        Cuadrado c;
        Punto p;
        int contador=1;
        while(i.hasNext()){
            c=(Cuadrado)i.next();
            System.out.println("Cuadrado N° "+contador);
            System.out.println("Angulo "+c.getAngulo());
            j=c.getPuntos().iterator();
            System.out.println("Puntos que forman el cuadrado ");
            while(j.hasNext()){               
                p=(Punto)j.next();
                System.out.println("Punto("+p.getColumna()+","+p.getFila()+")");
            }
            contador=contador+1;
        }
    }
   
}
***********************************************************************************
Clase principal del proyecto main:

package com.square.main;

import com.square.Logic.AlgoBusca;
import com.square.bean.Matriz;
import com.square.dao.DaoMatriz;
import java.util.Random;
import java.util.Scanner;

/**
 *
 * @author Administrador
 */
public class main {   
    public static void main(String arg[]){       
        System.out.println("Bienvenido al Sistema de reconocimiento de cuadrados");
        System.out.println("Crear Matriz:");
        Scanner teclado=new Scanner(System.in);
        System.out.print("Ingrese Numero de Filas:");
        int filas=teclado.nextInt();
        System.out.print("Ingrese Numero de Columnas:");
        int columnas=teclado.nextInt();
        Matriz m=DaoMatriz.generarMatriz(filas,columnas);
        DaoMatriz.paintMatriz(m);
        System.out.println("");
        System.out.println("Matriz de Unos");
        DaoMatriz.paintMatrizUnos(m);   
        System.out.println("Busqueda");
        System.out.println("CUADRADOS ANGULO 0:");
        AlgoBusca.imprimirCuadrados(AlgoBusca.buscarCuadradosAngulo0(m, DaoMatriz.paintMatrizUnos(m)));
        System.out.println("===============================================================");
        System.out.println("CUADRADOS ANGULO 45:");
        AlgoBusca.imprimirCuadrados(AlgoBusca.buscarCuadradosAngulo45(m, DaoMatriz.paintMatrizUnos(m)));
        System.out.println("===============================================================");
    }
}


Espero les haya gustado y servido. XD


Comentarios

  1. Jose Emilio Satornicio Chambergo9 de junio de 2012, 10:31 a.m.

    Podrías compartir el código fuente por favor... mi correo es joe-sacha@hotmail.com...gracias de antemano

    ResponderBorrar

Publicar un comentario

Entradas más populares de este blog

Emprendiendo en la Nube - Arquitectura y Patrón de Diseño

Imagen
Arquitectura Java para Desarrollo con GAE y GWT Soñando con el trabajo ideal, el cual sería ganar dinero por investigar, pues es lo que me gusta y  divierte, decidí emprender con una startup Tecnológica que pretende hacer de los lugares desconocidos y preciosos en lugares conocidos y visitados. Para  desarrollar una startup que pretende tener repercusión mundial, se necesita ser ordenado desde un principio, la arquitectura de software y el marco de trabajo en el proyecto es tu primera valla a superar. No pretendo criticar el desarrollo ágil por la poca documentación que genera, pienso que deberíamos tomar sus técnicas enriquecedoras, por eso combino el desarrollo clásico con el desarrollo ágil. Ahora ustedes se preguntarán por qué hablo de desarrollo ágil y clásico, si el título dice “Arquitectura Java para Desarrollo con GAE y GWT”, pues tiene mucha relación, pues los desarrolladores estamos acostumbrados a tomar  frameworks y buenas prácticas de diseño y desarrollo para a
Leer más

Extendiendo espacio de la partición raíz en linux en particiones estándar KVM - Debian 10

Ojo pestaña y ceja: Cuando realizas particiones estandar en Linux, la última partición que debes agregar es la raíz y esta debe ocupar los últimos sectores del disco. Esto porque cuando quieras extender la raíz(/) no te dará dolores de cabeza. Aquí un ejemplo en KVM /dev/vda1 swap 8G /dev/vda2 /boot 1G /dev/vda3 / 11G Extendiendo un disco virtual en qemu para KVM * Clonar KVM virt-clone --original vm_debian10_t2micro_ps --name vm_debian10_t2micro_servercapedwarf_one --file /opt/images/debian10_capedwarf_one-vm.qcow2 * Información de ubicación de disco virtual del kvm virsh domblklist vm_debian10_t2micro_servercapedwarf_one * Información de disco virtual virt-filesystems --long -h --all -a /opt/images/debian10_capedwarf_one-vm.qcow2 qemu-img info /opt/images/debian10_capedwarf_one-vm.qcow2  * Incrementar tamaño de disco virtual de 20G a 30G qemu-img resize /opt/images/debian10_capedwarf_one-vm.qcow2 +10G virsh blockresize vm_debian10_t2micro_servercapedwarf_one /opt/images/debian10_cape
Leer más