Advertisement
Guest User

Untitled

a guest
Apr 5th, 2020
246
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string mp[10];
  5. string mtx[10][10];
  6. bool visited[10][10];
  7. int xqX[] = {0,0,1,1,1,-1,-1,-1};
  8. int xqY[] = {1,-1,0,1,-1,0,1,-1};
  9. set<string> ans;
  10.  
  11. void solve(string check,int row,int col,int n,int m,int le){
  12.     if((le+1)==check.length()){
  13.         ans.insert(check);
  14.         return;
  15.     }
  16.     visited[row][col]=true;
  17.     for(int k=0;k<8;k++){
  18.         int dx=row+xqX[k];
  19.         int dy=col+xqY[k];
  20.         if( dx>=0 && dx<n && dy>=0 && dy<m && !visited[dx][dy] && mtx[dx][dy][0] == check[le+1])
  21.             solve(check,dx,dy,n,m,le+1);
  22.     }
  23.     visited[row][col]=false;
  24. }
  25.  
  26. void clear(){
  27.     ans.clear();
  28.     memset(visited,false,sizeof(visited));
  29. }
  30.  
  31. void process(){
  32.     clear();
  33.     int x,n,m;
  34.     cin >> x;
  35.     for(int i=0;i<x;i++)
  36.         cin>>mp[i];
  37.     cin >> n >> m;
  38.     for(int i=0;i<n;i++)
  39.         for(int j=0;j<m;j++)
  40.             cin>>mtx[i][j];
  41.    
  42.     for(int k=0;k<x;k++){
  43.         for(int i=0;i<n;i++){
  44.             for(int j=0;j<m;j++){
  45.                 if(mtx[i][j][0]==mp[k][0]){
  46.                     solve(mp[k],i,j,n,m,0);
  47.                 }
  48.             }
  49.         }
  50.     }
  51.    
  52.     if(ans.size()==0)
  53.         cout<<"-1";
  54.     else{
  55.         for(auto x:ans)
  56.             cout<<x<<" ";
  57.     }
  58.     cout << endl;
  59. }
  60.  
  61. int main(){
  62.     int T;
  63.     cin>>T;
  64.     while(T--) process();
  65.    
  66.     return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement