Retos - 016: Sopa de letras

Nivel de dificultad aproximado (1 a 5): 2  

Una sopa de letras consiste de un arreglo rectangular en cada una de cuyas posiciones se encuentra una letra minúscula. Además, se tiene una lista de palabras (formadas cada una exclusivamente por letras minúsculas) que se deben de buscar en el arreglo. Una palabra puede aparecer en línea recta en el arreglo en ocho posibles direcciones comenanzdo desde su primer letra: hacia arriba, hacia abajo, hacia la derecha, hacia la izquierda y en las cuatro direcciones diagonales. Además, una palabra puede aparecer en más de un lugar.

PROBLEMA

Deberás escribir un programa que reciba como entrada las dimensiones del arreglo rectangular, las letras que aparecen en el mismo, el tamaño de la lista y la lista de palabras a buscar y que determine cuántas veces aparece cada una de estas palabras en el arreglo.

ENTRADA

Tu programa deberá leer del teclado de la PC los siguientes datos

  • En la primera línea los números 0 < N, M <= 100 los cuales representan el número de renglones y el número de columnas del arreglo, respectivamente.
  • En cada una de las siguientes N líneas una cadena de M letras minúsculas, las cuales representan el arreglo.
  • En las siguientes líneas el número 0 < K <= 20000 que representa el tamaño de la lista de palabras.
  • En cada una de las siguientes K líneas una palabra P1 de 2 a 100 letras minúsculas.

SALIDA

Tu programa deberá escribir en la pantalla de la computadora K líneas y en cada una de ellas debe aparecer la cantidad X1 de veces que aparece la palabra P1

(Asegúrate de que has leído las preguntas frecuentes antes de plantear tu solución)

ENTRADA 
2 3
aal
ala
2
al
ala

SALIDA
6
2

Aportar una solución

Tu nombre (si quieres que aparezca):
Tu web/blog (si quieres que incluyamos un enlace a ella):
Tu e-mail (no se mostrará; si quieres que te avisemos cuando esté publicado):
¿Eres humano? ¿Cuánto es 2 más 3?
Lenguaje
Fuente:

// Ejemplo de solución para el reto 016
// Sopa de letras, por Luis_Angel
// Por Luis_Angel, 21-jun-2014
 
// Nota del recopilador: la solución no es totalmente correcta:
// Pide una palabra, en vez de leer desde la entrada estándar un contador y una serie de palabras
 
#include "iostream"
using namespace std;
int i,j,nf,nc;
int main()
{
        string pal;
        char sopa[100][100],palabra[100];
        int i,j,k,pf,pc,num_tot;
        bool esta;
        cin>>nf; // Filas
        cin>>nc; // Columnas
                for(i=0;i<nf;i++)
                        for(j=0;j<nc;j++)
                                cin>>sopa[i][j];
        /*cout<<"La sopa es\n";
                for(i=0;i<nf;i++)
                        {cout<<"\n\n";
                        for(j=0;j<nc;j++)
                                cout<<sopa[i][j]<<"\t";
                        }*/
        cout<<"\nIngrese una palabra para buscar: ";cin>>pal;
 
                for(i=0;i<pal.length();i++)
                palabra[i]=pal.at(i);
 
        num_tot=0;
        esta=false;
 
                for(i=0;i<nf;i++)
                        for(j=0;j<nc;j++)
                        if(palabra[0]==sopa[i][j])
                        {
                                for(k=1;k<pal.length();k++)
                                {
                                        if(sopa[i][j+k]==palabra[k] && (j+k)<nc)
                                        esta=true;
                                        else
                                        {esta=false;
                                        break;
                                        }
                                }
                                if(esta==true)
                                num_tot++;
                        }
 
 
                for(i=0;i<nf;i++)
                        for(j=0;j<nc;j++)
                        if(palabra[0]==sopa[i][j])
                        {
                                for(k=1;k<pal.length();k++)
                                {
                                        if(sopa[i][j-k]==palabra[k] && (j-k)>=0)
                                        esta=true;
                                        else
                                        {esta=false;
                                        break;
                                        }
                                }
                                if(esta==true)
                                num_tot++;
                        }
 
 
                for(i=0;i<nf;i++)
                        for(j=0;j<nc;j++)
                        if(palabra[0]==sopa[i][j])
                        {
                                for(k=1;k<pal.length();k++)
                                {
                                        if(sopa[i+k][j]==palabra[k] && (i+k)<nf)
                                        esta=true;
                                        else
                                        {esta=false;
                                        break;
                                        }
                                }
                                if(esta==true)
                                num_tot++;
                        }
 
 
                for(i=0;i<nf;i++)
                        for(j=0;j<nc;j++)
                        if(palabra[0]==sopa[i][j])
                        {
                                for(k=1;k<pal.length();k++)
                                {
                                        if(sopa[i-k][j]==palabra[k] && (i-k)>=0)
                                        esta=true;
                                        else
                                        {esta=false;
                                        break;
                                        }
                                }
                                if(esta==true)
                                num_tot++;
                        }
 
 
                for(i=0;i<nf;i++)
                        for(j=0;j<nc;j++)
                        if(palabra[0]==sopa[i][j])
                        {
                                for(k=1;k<pal.length();k++)
                                {
                                        if(sopa[i+k][j+k]==palabra[k] && (i+k)<nf && (j+k)<nc)
                                        esta=true;
                                        else
                                        {esta=false;
                                        break;
                                        }
                                }
                                if(esta==true)
                                num_tot++;
                        }
 
                for(i=0;i<nf;i++)
                        for(j=0;j<nc;j++)
                        if(palabra[0]==sopa[i][j])
                        {
                                for(k=1;k<pal.length();k++)
                                {
                                        if(sopa[i-k][j-k]==palabra[k] && (i-k)>=0 && (j-k)>=0)
                                        esta=true;
                                        else
                                        {esta=false;
                                        break;
                                        }
                                }
                                if(esta==true)
                                num_tot++;
                        }
 
        cout << num_tot<< endl;
return 0;
}

// Ejemplo de solución para el reto 016
// Sopa de letras, por Caranim
// Por Caranim, 08-jul-2014
 
// Nota del recopilador:
// La lógica es buena, pero no es una solución totalmente válida,
// Por mostrar información adicional en pantalla
// Y emplear colores y Readkey
 
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
/* ------------------------------------------------------------------------------------------------------------------------------------------*
 
Reto: 16 ( Sopa de letras ).
 
 *Ejemplo de entrada propuesto originalmente en la especificación del Reto.
ENTRADA
2 3
aal
ala
2
al
ala
 
SALIDA
6
2
 
 ________________________________________________________________________________________
 
 Ejemplo para un fichero de entrada.
 Pegar todas las líneas en un archivo de texto plano con nombre "MatrizLetras.txt" para poder ejecutar la solución.
 
15 15
foktaicergniica
grtcuyagtreuniv
rtaathurdtcmcbf
einntcflouheior
cliacivomprsaba
iytdyiitageuron
ffpasiatdbfwcnc
rawtkilvhsbcaai
axwsfdaudqdxnhn
nzxibdaiutvaajd
cekmaeyiefdgdei
irondssrlakbaaa
tcayrurnoruegai
sgrecianoruegaa
agailatitaliatr
7
italia
grecia
canada
india
peru
francia
noruega
 */
 
namespace Sopa_de_Letras
{
    class Program
    {
        static string[] sopa_filas;
        static ListaBuscar[] palabras_objetivo;
 
        static void Main(string[] args)
        {
            bool tmpbool;
            Console.BackgroundColor = ConsoleColor.White;
            Console.ForegroundColor = ConsoleColor.DarkGray;
            Console.Clear();
 
            // Proceso para cargar datos. El enunciado pide que sea via teclado, pero de esta manera es más rápido testar el programa.
            if (File.Exists("C:\\Ejercicios programacion\\SopaLetras\\Sopa de Letras\\MatrizLetras.txt"))
            {
                tmpbool = Cargar_Datos_Fichero("C:\\Ejercicios programacion\\SopaLetras\\Sopa de Letras\\MatrizLetras.txt");
            }
                else{
                    tmpbool = Cargar_Datos_Teclado();
                }
 
 
        if (tmpbool)
            {
                // Proceso de búsqueda.
                foreach (ListaBuscar objetivos in palabras_objetivo)
                {
                    // Buscar para cada uno de los 8 posibles sentidos.
                    for (int fila_actual = 0; fila_actual < sopa_filas.Length; fila_actual++)
                    {
                        for (int col_actual = 0; col_actual < sopa_filas[fila_actual].Length; col_actual++)
                        {
                            for (int incx = -1; incx < 2; incx++)
                            {
                                for (int incy = -1; incy < 2; incy++)
                                {
                                    if (!(incx == 0 && incy == 0))
                                    {
                                        if (buscar_palabra(objetivos.palabra(), fila_actual, col_actual, incx, incy))
                                        {
                                            objetivos.encontrada();
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
 
                // Proceso de muestra de resultados.
                foreach (ListaBuscar objetivos in palabras_objetivo)
                {
                    Console.WriteLine("{0}  --> {1} Veces.", objetivos.palabra(), objetivos.veces());
                }
            }
            else
            {
                Console.WriteLine("El proceso de carga de datos ha fallado.");
            }
 
            Console.ReadKey(); // Pausa para que la pantalla no se cierre al terminar el proceso y podamos ver los resultados.
        }
 
        static bool Cargar_Datos_Teclado()
        {
            // Primera línea de datos: Nº de filas y columnas de nuestra Sopa de letras.
            string linealeida;
            int filas, columnas;
 
            Console.WriteLine ("Introduce el número de FILAS y COLUMNAS de la Sopa de letras separados por un Espacio.");
            linealeida = Console.ReadLine();
 
            filas = Convert.ToInt32(linealeida.Substring(0, linealeida.IndexOf(" ")));
            columnas = Convert.ToInt32(linealeida.Substring(linealeida.IndexOf(" ")));
            sopa_filas = new string[filas];
 
            // Cargar los caracteres de la matriz.
            for (int indice = 0; indice < filas; indice++)
            {
                Console.WriteLine("Introduce la fila número {0} de la Sopa de Letras.", indice+1);
                linealeida = Console.ReadLine();
                  if (linealeida.Length < columnas) // Por si nos falta algún caracter en alguna de las líneas.
                {
                    Console.WriteLine("La línea " + indice  + " no tiene el número de caracteres necesarios.");
                }
                sopa_filas[indice] = linealeida.Substring(0,columnas); // Para que no tome más columnas de las debidas.
            }
            // Capturar el número de palabras a buscar y las palabras.
            Console.Clear();
             Console.WriteLine("Introduce el número de palabras a buscar.");
             linealeida = Console.ReadLine();
            palabras_objetivo = new ListaBuscar[Convert.ToInt32(linealeida)];
            for (int indice = 0; indice < palabras_objetivo.Length; indice++)
            {
                Console.WriteLine("Escribe la palabra a buscar Num. {0}.", indice);
                linealeida = Console.ReadLine();
                if (linealeida.Length < 2 )
                {
                    Console.WriteLine("No se admiten palabras de menos de dos caracteres.\n Se cancela el proceso.");
                    Console.ReadKey(); // Para hacer una pausa y dar tiempo a leer el mensaje.
                    return false;
                }
                palabras_objetivo[indice] = new ListaBuscar(linealeida);
            }
            return true;
            }
 
        static bool Cargar_Datos_Fichero(string nombrefichero)
         // Retorna "true" si la carga se ha producido sin problemas.Solo devuelve False si el fichero no existe o alguna de las palabras objetivo
         // tiene longitud inferior a 2 caracteres , pero realmentese pueden dar bastantes más casos que no están contemplados en esta solución.
        {
            StreamReader fich_datos;
            string linealeida;
            int filas, columnas;
 
            fich_datos = new StreamReader(nombrefichero);
            // Comprobar que el fichero exista.
            if (!System.IO.File.Exists(nombrefichero))
            {
                Console.WriteLine("No existe el fichero " + nombrefichero);
                return false;
            }
            fich_datos = File.OpenText(nombrefichero);
            // Empezamos a leer el fichero y a cargar los valores necesarios.
            linealeida = fich_datos.ReadLine();
            // Cargamos el número de filas y columnas que vamos a necesitar.
            filas = Convert.ToInt32(linealeida.Substring(0, linealeida.IndexOf(" ")));
            columnas = Convert.ToInt32(linealeida.Substring(linealeida.IndexOf(" ")));
            sopa_filas = new string[filas];
            // Cargamos los caracteres de la matriz de la Sopa de Letras.
            for (int indice = 0; indice < filas; indice++)
            {
                linealeida = fich_datos.ReadLine();
                if (linealeida.Length < columnas) // Por si nos falta algún caracter en alguna de las líneas.
                {
                    Console.WriteLine("La línea " + indice  + " no tiene el número de caracteres necesarios.");
                    fich_datos.Close();
                    return false;
                }
                sopa_filas[indice] = linealeida.Substring(0,columnas); // Para que no tome más columnas de las debidas.
            }
            // Cargamos el número de palabras a buscar.
            linealeida = fich_datos.ReadLine();
            palabras_objetivo = new ListaBuscar[Convert.ToInt32(linealeida)];
            for (int indice = 0; indice < palabras_objetivo.Length; indice++)
            {
                linealeida = fich_datos.ReadLine();
                if (linealeida.Length < 2 )
                {
                    Console.WriteLine("No se admiten palabras de menos de dos caracteres.\n Se cancela el proceso.");
                    Console.ReadKey(); // Para hacer una pausa y dar tiempo a leer el mensaje.
                    return false;
                }
                palabras_objetivo[indice] = new ListaBuscar(linealeida);
            }
 
            fich_datos.Close();
            return true;
        }
 
    static bool buscar_palabra(string palabra, int xinicial, int yinicial, int inc_x, int inc_y)
{
        bool retorno = false;
        bool seguir = true;
        int iteraciones = 0;
 
        while (seguir)
        {
            if (xinicial < 0 || yinicial < 0 || xinicial + 1 > sopa_filas.Length || yinicial + 1 > sopa_filas[0].Length)
            {
                seguir = false;
            }
            else
            {
                if (palabra.Substring(iteraciones, 1) == sopa_filas[xinicial].Substring(yinicial, 1))
                {
                    iteraciones++;
                    xinicial += inc_x;
                    yinicial += inc_y;
                    if (iteraciones == palabra.Length ) // Hemos encontrado una coincidencia.
                    {
                        retorno = true;
                        seguir = false;
                    }
                }
                else
                {
                    seguir = false;
                }
            }
        }
 
    return retorno;
 
}
    }
 
    class ListaBuscar
        // Guarda las palabras y las veces que la hemos encontrado.
    {
        string _palabra;
        int  _veces;
 
    public  ListaBuscar(string palabra)
    {
        _palabra = palabra;
        _veces = 0;
    }
    public string veces()
    {
        return _veces.ToString().Trim();
    }
    public string palabra()
    {
        return _palabra;
    }
    public int Longitud()
    {
        return _palabra.Length;
    }
    public void encontrada()
    {
        _veces++;
    }
 
    }