fork(3) download
copy 
  1. /*
  2. Given a grid of characters of size n*m and q words in a dictionary.
  3. Print the words that lie in the grid. (Diagonal movement allowed)
  4.  
  5. Data Structure Used - Trie
  6. Time Complexity - O(n*m*k) where k is the length of the longest word in the dictionary
  7.  
  8. Author - hiteshpardasani99
  9. */
  10.  
  11. #include<bits/stdc++.h>
  12. #define ll long long
  13. #define pb push_back
  14. #define ff first
  15. #define ss second
  16. #define pll pair<ll,ll>
  17. using namespace std;
  18.  
  19. struct node
  20. {
  21.     bool leaf;  //if the node is a leaf then, a word in the dictionary ends at this node.
  22.     node* child[26];
  23. };
  24.  
  25. node* create()
  26. {
  27.     node* ret = new node();
  28.     for(int i=0;i<26;i++)ret->child[i]=NULL;
  29.     ret->leaf=false;
  30.     return ret;
  31. }
  32.  
  33. ll n,m,q;
  34. char grid[1001][1001];  //input grid
  35. int vis[1001][1001];    //visit array for dfs
  36. string dict[100005];    //Dictionary
  37. vector<char> ans;
  38. set<vector<char>> s;    //Set to store the answer
  39. pll dir[8]={{-1,-1},{-1,0},{-1,1},{0,1},{0,-1},{1,1},{1,0},{1,-1}};
  40.  
  41. node* root=create();
  42.  
  43. void add(string x)
  44. {
  45.     node* ex=root;  // to keep a copy of root
  46.     for(int i=0;i<x.length();i++)
  47.     {
  48.         if(root->child[x[i]-'a']==NULL)
  49.         {
  50.             root->child[x[i]-'a']=create();
  51.         }
  52.         root=root->child[x[i]-'a'];
  53.     }
  54.     root->leaf=true;
  55.     root=ex;
  56. }
  57.  
  58. bool check(pll ne)
  59. {
  60.     return (ne.ff>=0&&ne.ss>=0&&ne.ff<n&&ne.ss<m);
  61. }
  62.  
  63. void dfs(pll c)
  64. {
  65.     if(root->child[grid[c.ff][c.ss]-'a']!=NULL) //if the current char is present in trie
  66.     {
  67.         node *ex=root;
  68.         root = root->child[grid[c.ff][c.ss]-'a'];
  69.         ans.pb(grid[c.ff][c.ss]);
  70.         vis[c.ff][c.ss]=1;
  71.         for(int i=0;i<8;i++)        //to check in all the directions
  72.         {
  73.             pll ne={c.ff+dir[i].ff,c.ss+dir[i].ss};
  74.             if(check(ne)&&!vis[ne.ff][ne.ss])
  75.             {
  76.                 dfs(ne);
  77.             }
  78.         }
  79.         root=ex;
  80.         ans.pop_back();
  81.         vis[c.ff][c.ss]=0;
  82.     }
  83.     else
  84.     {
  85.         if(root->leaf && ans.size())
  86.         {
  87.             s.insert(ans);
  88.         }
  89.     }
  90. }
  91.  
  92. void solve()
  93. {
  94.     node* ex=root;
  95.     for(int i=0;i<n;i++)
  96.     {
  97.         for(int j=0;j<m;j++)
  98.         {
  99.             pll curr={i,j};
  100.             root = ex;
  101.             dfs(curr);  //check from every possible starting point
  102.         }
  103.     }
  104.     for(auto it=s.begin();it!=s.end();it++)
  105.     {
  106.         vector<char> v=*it;
  107.         for(int i=0;i<v.size();i++)cout<<v[i];cout<<endl;
  108.     }
  109. }
  110.  
  111.  
  112. int main()
  113. {
  114.     cin>>n>>m;
  115.     for(int i=0;i<n;i++)
  116.     {
  117.         for(int j=0;j<m;j++)cin>>grid[i][j];
  118.     }
  119.     cin>>q;
  120.     for(int i=0;i<q;i++)
  121.     {
  122.         cin>>dict[i];
  123.         add(dict[i]);
  124.     }
  125.     solve();
  126.     return 0;
  127. }
  128.  
Success #stdin #stdout 0s 23256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FcLqQw
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!