fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <map>
  5. #include <algorithm>
  6. #include <iterator>
  7.  
  8. using namespace std;
  9.  
  10. struct node{
  11.     map<char, int> next;
  12.     int cnt=0;
  13. };
  14.  
  15. struct tr{
  16.     vector<node> go;
  17.     tr(){
  18.         go.resize(1);
  19.     }
  20.     void add_str(string &s){
  21.         int q=0;
  22.         for(char ch: s){
  23.             if(!go[q].next.count(ch)){
  24.                 go[q].next[ch]=go.size();
  25.                 q=go.size();
  26.                 go.resize(go.size()+1);
  27.             }
  28.             else{
  29.                 go[q].next[ch];
  30.             }
  31.         }
  32.         ++go[q].cnt;
  33.     }
  34. };
  35.  
  36.  
  37. bool dfs(vector<string> &grid, vector<vector<int>> &used, int i, int j, vector<node> &go, int q){
  38.     if(used[i][j]){
  39.         return false;
  40.     }
  41.     used[i][j]=1;
  42.     if(go[q].cnt){
  43.         --go[q].cnt;
  44.         return true;
  45.     }
  46.  
  47.     int n=used.size(), m=used[0].size();
  48.  
  49.     if(i<n-1 && go[q].next.count(grid[i+1][j])){
  50.         bool res=dfs(grid, used, i+1, j, go, go[q].next[grid[i+1][j]]);
  51.         if(res){
  52.             return true;
  53.         }
  54.     }
  55.  
  56.     if(i>0 && go[q].next.count(grid[i-1][j])){
  57.         bool res=dfs(grid, used, i-1, j, go, go[q].next[grid[i-1][j]]);
  58.         if(res){
  59.             return true;
  60.         }
  61.     }
  62.  
  63.     if(j<m-1 && go[q].next.count(grid[i][j+1])){
  64.         bool res=dfs(grid, used, i, j+1, go, go[q].next[grid[i][j+1]]);
  65.         if(res){
  66.             return true;
  67.         }
  68.     }
  69.  
  70.     if(j>0 && go[q].next.count(grid[i][j-1])){
  71.         bool res=dfs(grid, used, i, j-1, go, go[q].next[grid[i][j-1]]);
  72.         if(res){
  73.             return true;
  74.         }
  75.     }
  76.  
  77.  
  78.     used[i][j]=0;
  79.     return false;
  80. }
  81.  
  82. int main()
  83. {
  84.     int n, m, p; cin>>n>>m>>p;
  85.  
  86.     vector<string> grid(n);
  87.     vector<vector<int>> used(n, vector<int> (m, 0));
  88.     tr trie;
  89.  
  90.     for(int i=0; i<n; ++i)
  91.         cin>>grid[i];
  92.  
  93.     for(int i=0; i<p; ++i){
  94.         string s; cin>>s;
  95.         trie.add_str(s);
  96.     }
  97.  
  98.     for(int i=0; i<n; ++i)
  99.         for(int j=0; j<m; ++j)
  100.             if(trie.go[0].next.count(grid[i][j]))
  101.                 dfs(grid, used, i, j, trie.go, trie.go[0].next[grid[i][j]]);
  102.  
  103.     vector<char> ans;
  104.     for(int i=0; i<n; ++i)
  105.         for(int j=0; j<m; ++j)
  106.             if(!used[i][j])
  107.                 ans.push_back(grid[i][j]);
  108.  
  109.     sort(ans.begin(), ans.end());
  110.  
  111.     copy(ans.begin(), ans.end(), ostreambuf_iterator<char>(cout));
  112.  
  113.  
  114.     return 0;
  115. }
  116.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
3 3 1
axx
bcy
zzz
abc
stdout
copy 
xxyzzz
https://ideone.com/06yGHW
language:
C++14 (clang 8.0)
created:
7 years ago
visibility:
public

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!