bisqueda de una fila y columna en una matriz

[darkChild]

Buenas gnt mi primer tema en el foro bueno el tema en cuestiones el sgte. debo buscar en una matriz una fila y una columna determinada el problema no es este sino lo q qiero saber s si hay un a manera de acr q la busqda sea optima lo q ic fue una busqda secuencial 1ª x fila y luego por columna.

Lo q qiero saber s si alguien conoc 1 libro dnd lo pueda leer o si m da una mano para mejorarlo

Muchas gracias.

Saludos.

[cristian_qc]

A qué te referís con "buscar fila y columna" ?. Y qué tipo de matriz es ?

[darkChild]

El tema es asi debo buscar en una matrix n x n (cuadrada) si existe al menos una fila y columna completa de unos y ceros noc si me explico bien

[cesar_casla]

Hola! no creo q haya un libro que tenga un metodo para lo que vos necesitas. El ejercicio que propones es mas de practica que otra cosa.. Lo que podrias hacer es subir el codigo que hiciste y ver si se puede mejorar

Saludos

[sam90]

Suponiendo que todos los elementos son enteros positivos. Sino se le puede hacer unos retoques podrias sumar todos los elementos de las filas o columnas y ver cual es esa suma.

Si una columna tiene todo cero, la suma de todos los elementos de esta columna tiene que dar cero. Si son todos uno la suma daria N.

La idea seria la siguiente:
Supongamos que tenemos una matriz NxN. entonces definimos una matriz N+1 X N+1

Código C:

int matriz[N+1][N+1];
 
for(i=0;i< N ; i++)
    for(j=0;j< N ; j++) {
        matriz[i][N] += matriz[i][j];
        matriz[N][j] += matriz[i][j]; 
     }
 

Luegos comparas los elementos como te dije. Esto es lo mas rapido que se me ocurre por el momento. Solo se recorre una vez la matriz y podes determinar todas las columnas o filas que decis.

Saludos,
Espero que se entienda.

[darkChild]

De esa manera estaria recorriendo todas las filas de la matriz si entiendo bien...
Pongamoslo de esta manera si por ejemplo estoy buscando una fila toda de ceros entonces como decis si la fila es asi :

00001000

yo segun tu metodo sabria q no es enteramente de ceros cndo termine de sumar o sea al final de recorrerla (por favor corregime si no estoy en lo cierto ),en cambio si coloco un corte de control en el caso de buscar una fila de ceros debo verificar que no aparezca algun uno en caso de haber la busqueda termina de este modo tengo en el peor de los casos el uno estaria en la ult posicion y en el mejor caso en la primera tu metodo no me diria si es cero completo sino hasta la ultima en el peor y en el mjor de los casos ...

no c si me explico bien si talvez mi forma de pensarlo te parec erronea hazmelo saber por favor estoy para aprender y muchas gracias por la respuesta.

Saludos!!

[sam90]

Te explicaste bien...pero antes de esa explicacion vos estabas buscando filas y columnas con todos ceros o todos unos...ahora me cambiaste el ejercicio...solo buscas filas o columnas con ceros.

Pero lo que tu piensas esta bien...

[darkChild]

No bueno el ejemplo q di era para ceros pero aplica igualmente para unos.. el ejercicio es asi buscar filas y columnas de unos y ceros

[cristian_qc]

Yo creía que lo que pedías era encontrar una fila, digamos " 0,1,0" en una matriz, digamos:
0, 1, 0
1, 1, 1
0, 1, 0.

En este caso hay que recorrer fila por fila, o columna por columna, y comparar los elementos.
En el caso de que quieras saber si una fila/columna está compuesta enteramente por el mismo número, pasas dicho número a una función que recorra las filas/columnas y retorne falso exactamente cuando encuentre el número pasado como parámetro, o verdadero cuando finaliza el recorrido.
Es decir que si se encuentra un número diferente no se recorre el resto de la fila/columna.

[darkChild]

Si si lo que hice es algo asi

Código C++:

#include "busqueda.h"
 
using namespace std;
 
/*Metodo que al recibir
 * un argumento de tipo string
 * identifica si la busqueda
 * es por columna o fila
 * utiliza un corte de control que identifica
 * si hay cemento en caso contrario devuelve TRUE
 * */
bool buscarCaminoTierra(int matriz[MAXIMO][MAXIMO],int ultpos,int indice,string tipoBusqueda){
 
    bool encontrado  = true;
    bool esCemento = false;
 
    if(tipoBusqueda == FILA){
        for(int i = 0;i < ultpos && !esCemento;i++){
            cout<<"Buscando camino de tierra"<<endl;
            if(matriz[indice][i] == CEMENTO)
                esCemento = true;
        }
    }else
        for(int i = 0;i < ultpos && !esCemento;i++){
            cout<<"Buscando camino de tierra"<<endl;
            if(matriz[i][indice] == CEMENTO)
                esCemento = true;
        }
 
    return (encontrado = esCemento == false ? encontrado : !encontrado);
 
}
/*Metodo que al recibir
 * un argumento de tipo string
 * identifica si la busqueda
 * es por columna o fila
 * utiliza un corte de control que identifica
 * si hay tierra en caso contrario devuelve TRUE
 * */
bool buscarCaminoCemento(int matriz[MAXIMO][MAXIMO],int ultpos,int indice,string tipoBusqueda){
 
    bool encontrado  = true;
    bool esTierra = false;
 
    if(tipoBusqueda == FILA){
        for(int i = 0;i < ultpos && !esTierra;i++){
            cout<<"Buscando camino de cemento"<<endl;
            if(matriz[indice][i] == TIERRA)
                esTierra = true;
        }
    }else
        for(int i = 0;i < ultpos && !esTierra;i++){
            cout<<"Buscando camino de cemento"<<endl;
            if(matriz[i][indice] == TIERRA)
                esTierra = true;
        }
 
    return (encontrado = esTierra == false ? encontrado : !encontrado);
 
}
/*Busca por fila tanto tierra como cemento
 * si encuentra una ocurrencia de ambos sale caso
 * contrario sigue la busqueda
 * */
void buscarCaminoFila(int matriz[MAXIMO][MAXIMO],int rangoFila,int rangoCol){
 
    cout<<BUSQUEDA_FILA<<endl;
    bool buscoCemento = false;bool buscoTierra = false;
    int encontroCemento = 0;
    int encontroTierra  = 0;
    for(int i = 0;(!encontroCemento == 1 || !encontroTierra == 1) && i < rangoFila ;i++){
        buscoCemento = buscarCaminoCemento(matriz,rangoCol,i,FILA) == true ? true : false;
        controloBusqueda(buscoCemento,buscoTierra,encontroCemento,encontroTierra,i,FILA);
        buscoTierra  = buscarCaminoTierra(matriz,rangoCol,i,FILA)  == true ? true : false;
        controloBusqueda(buscoCemento,buscoTierra,encontroCemento,encontroTierra,i,FILA);
    }
}
/*Busca por columna tanto tierra como cemento
 * si encuentra una ocurrencia de ambos sale caso
 * contrario sigue la busqueda
 * */
void buscarCaminoColumna(int matriz[MAXIMO][MAXIMO],int rangoFila,int rangoCol){
 
    cout<<BUSQUEDA_COLUMNA<<endl;
    bool buscoCemento,buscoTierra;
    int encontroCemento = 0;
    int encontroTierra  = 0;
    for(int i = 0;(!encontroCemento == 1 || !encontroTierra == 1) && i < rangoCol ;i++){
        buscoTierra  = buscarCaminoTierra(matriz,rangoFila,i,COL)  == true ? true : false;
        controloBusqueda(buscoCemento,buscoTierra,encontroCemento,encontroTierra,i,COL);
        buscoCemento = buscarCaminoCemento(matriz,rangoFila,i,COL) == true ? true : false;
        controloBusqueda(buscoCemento,buscoTierra,encontroCemento,encontroTierra,i,COL);
    }
}
/*Se encarga de verificar si hay un
 * suceso de cemento o tierra recibiendo un parametro
 * bool de ambos e incrementa al recibir un TRUE de uno
 * de los dos o ambos e imprime el resultado*/
void controloBusqueda(bool buscoCemento,bool buscoTierra,int &encontroCemento,int &encontroTierra,int indice,string filaCol){
 
    if(buscoCemento || buscoTierra){
        if(buscoCemento){
            encontroCemento++;
            printResult(indice,encontroCemento,CEMENTO,filaCol);
        }
        if(buscoTierra){
            encontroTierra++;
            printResult(indice,encontroTierra,TIERRA,filaCol);
        }
    }else
        printResult(indice,encontroTierra,TIERRA,filaCol);
}
 
 
void buscarCaminos(int matriz[MAXIMO][MAXIMO],int rangoFila,int rangoCol){
 
    buscarCaminoFila(matriz,rangoFila,rangoCol);
    buscarCaminoColumna(matriz,rangoFila,rangoCol);
    mostrarResultado(matriz,rangoFila,rangoCol);
 
}
 
/*Formatea la salida por consola
 * identificando si es fila o columna */
void printResult(int fila,int encontro,int tipo,string filaCol){
 
    stringstream ss;
    string frase;
    ss<<++fila;
    frase = filaCol == COL ? "Encontro en " + COL + " " + ss.str() : "Encontro en " + FILA + " " +ss.str();
    frase = tipo == CEMENTO ? frase + " Cemento": frase + " Tierra";
    frase = encontro == 1 ? frase : "No encontro";
    cout<<frase<<endl;
}
 

digan si se puede mejorar gracias !!!