SHARE
TWEET

Untitled

a guest Oct 23rd, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #include <string>
  3. using namespace std;
  4. int N,M,Q;
  5. vector< pair<int,int> > chars[26];
  6. char graph[100][100];
  7. bool visited[100][100];
  8. vector <string> queries;
  9. char c;
  10. void read(){
  11.     cin >> N  >> M;
  12.     //for(int i=0;i<N*M;cin>>graph[i/N][i%M],i++);
  13.     for(int i=0;i<N;i++)
  14.         for(int j=0;j<M;j++){
  15.             cin >> c;
  16.             chars[c-'a'].push_back(make_pair(i,j));
  17.             graph[i][j] = c;
  18.         }
  19.     /*
  20.         5 5
  21.         p n x g f
  22.         l p w g z
  23.         j p b k p
  24.         h p c z a
  25.     */
  26.     for(int i=0;i<N*M;cout<<graph[i/N][i%M],i++);
  27.     cin >> Q;
  28.     while(Q--){
  29.         string tmp;
  30.         cin >> tmp;
  31.         cout << tmp;
  32.         queries.push_back(tmp);
  33.     }
  34. }
  35. bool valid_pos(int x,int y){
  36.     return x>=0&&x<N&&y>=0&&y<M&&!visited[x][y];
  37. }
  38. string to_string(int s){
  39.     string st = "";
  40.     while(s>0){
  41.         int t = s%10;
  42.         s = s/10;
  43.         st = st + char(t+'0');
  44.     }
  45.     return st;
  46. }
  47. string find_sol(int x,int y,string s,int idx){
  48.     if(idx == s.size()) return to_string(x)+","+to_string(y);
  49.     visited[x][y] = true;
  50.     if(valid_pos(x+1,y) && graph[x+1][y] == s[idx]){
  51.         return find_sol(x+1,y,s,idx+1);
  52.     }
  53.     if(valid_pos(x,y+1) && graph[x][y+1] == s[idx]){
  54.         return find_sol(x,y+1,s,idx+1);
  55.     }
  56.     if(valid_pos(x-1,y) && graph[x-1][y] == s[idx]){
  57.         return find_sol(x-1,y,s,idx+1);
  58.     }
  59.     if(valid_pos(x,y-1) && graph[x][y-1] == s[idx]){
  60.         return find_sol(x,y-1,s,idx+1);
  61.     }
  62.     if(valid_pos(x+1,y+1) && graph[x+1][y+1] == s[idx]){
  63.         return find_sol(x+1,y+1,s,idx+1);
  64.     }
  65.     if(valid_pos(x+1,y-1) && graph[x+1][y-1] == s[idx]){
  66.         return find_sol(x+1,y-1,s,idx+1);
  67.     }
  68.     if(valid_pos(x-1,y-1) && graph[x-1][y-1] == s[idx]){
  69.         return find_sol(x-1,y-1,s,idx+1);
  70.     }
  71.     if(valid_pos(x-1,y+1) && graph[x-1][y+1] == s[idx]){
  72.         return find_sol(x-1,y+1,s,idx+1);
  73.     }
  74.     visited[x][y] = false;
  75.     return "-1";
  76. }
  77. void solve(){
  78.     for(int i=0;i<queries.size();i++){
  79.         c = queries[i][0];
  80.         for(int j=0;j< chars[c-'a'].size();j++){
  81.             pair<int,int> p = chars[c-'a'][j];
  82.             if(valid_pos(p.first,p.second)){
  83.                 string s = find_sol(p.first,p.second,queries[i],1);
  84.                 if(s!="-1"){
  85.                     cout<<queries[i]<<endl;
  86.                     cout<<p.first<<","<<p.second<<endl;
  87.                     cout<<s<<endl;
  88.                     break;
  89.                 }
  90.             }
  91.             }
  92.         }
  93. }
  94. int main(){
  95. read();
  96. solve();
  97.     return 0;
  98. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top