Question Name:Word Boggle

#include <stdio.h>
#include<string.h>
#include<stdlib.h>

int strcmpfunc(const void *a, const void *b)
{
    return (strcmp((char *)a, (char *)b));
}
int main()
{
    int tst;
    scanf("%d",&tst);

    while(tst--)
    {
        int strings;
        scanf("%d",&strings);

        char str[strings][20];
        int i;
        for(i = 0; i<strings; i++)
           scanf(" %s",str[i]);
           
        /*Sort the array.*/
        qsort(str, strings, sizeof(char)*20, strcmpfunc);
        
        int pre_index = 0;
        /*Remove duplicate*/
        for(i = 1; i<strings; i++)
        {
            if (!strcmp(str[i], str[pre_index]))
              str[i][0] = '\0';
            else
              pre_index = i;
        }

        int ch[82], str_ch[82], no_word = 1;

        for(i = 0; i<82; i++)
        {
            ch[i] = 0;
            str_ch[i] = 0;
        }
        
        int x, y, j;
        scanf("%d", &x);
        scanf("%d", &y);

        for(j = 0; j<x*y; j++)
        {
            char input;
            scanf(" %c", &input);
            ch[input-'A']++;
        }

        for (i = 0; i<strings; i++)
        {
            if (!strlen(str[i]))
              continue;
            for(j = 0; j<82; j++)
              str_ch[j] = 0;
            
            for (j = 0; j<strlen(str[i]); j++)
                str_ch[str[i][j]-'A']++;

            for(j = 0; j<82; j++)
               if (str_ch[j] && str_ch[j] > ch[j])
                 break;

            if (j == 82)
            {
                printf("%s ",str[i]);
                no_word = 0;
            }
        }
        
        if (no_word)
          printf("-1");
        printf("\n");
    }
	return 0;
}
  • Problem Description


    Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. 

    Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.

    Example:

    Input: dictionary[] = {“GEEKS”, “FOR”, “QUIZ”, “GO”};
    boggle[][] = {{‘G’,’I’,’Z’},
    {‘U’,’E’,’K’},
    {‘Q’,’S’,’E’}};

    Output: Following words of dictionary are present GEEKS, QUIZ

    Input:
    The first line of input contains an integer T denoting the no of test cases . Then T test cases follow. Each test case contains an integer x denoting the no of words in the dictionary. 

    Then in the next line are x space separated strings denoting the contents of the dictionary. In the next line are two integers N and M denoting the size of the boggle. The last line of each test case contains NxM space separated values of the boggle.

    Output:
    For each test case in a new line print the space separated sorted distinct words of the dictionary which could be formed from the boggle. If no word can be formed print -1.

    Constraints:
    1<=T<=10
    1<=x<=10
    1<=n,m<=7


  • Test Case 1
    Input (stdin)1
    4
    GEEKS FOR QUIZ GO
    3 3
    G I Z U E K Q S E
    Expected OutputGEEKS QUIZ
  • Test Case 2
    Input (stdin)1
    4
    SRM UNIV KTR CSE
    3 3
    U S N R V M I
    Expected OutputSRM UNIV

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.