Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #include <string>
- using namespace std;
- int N,M,Q;
- vector< pair<int,int> > chars[26];
- char graph[100][100];
- bool visited[100][100];
- vector <string> queries;
- char c;
- void read(){
- cin >> N >> M;
- //for(int i=0;i<N*M;cin>>graph[i/N][i%M],i++);
- for(int i=0;i<N;i++)
- for(int j=0;j<M;j++){
- cin >> c;
- chars[c-'a'].push_back(make_pair(i,j));
- graph[i][j] = c;
- }
- /*
- 5 5
- p n x g f
- l p w g z
- j p b k p
- h p c z a
- */
- for(int i=0;i<N*M;cout<<graph[i/N][i%M],i++);
- cin >> Q;
- while(Q--){
- string tmp;
- cin >> tmp;
- cout << tmp;
- queries.push_back(tmp);
- }
- }
- bool valid_pos(int x,int y){
- return x>=0&&x<N&&y>=0&&y<M&&!visited[x][y];
- }
- string to_string(int s){
- string st = "";
- while(s>0){
- int t = s%10;
- s = s/10;
- st = st + char(t+'0');
- }
- return st;
- }
- string find_sol(int x,int y,string s,int idx){
- if(idx == s.size()) return to_string(x)+","+to_string(y);
- visited[x][y] = true;
- if(valid_pos(x+1,y) && graph[x+1][y] == s[idx]){
- return find_sol(x+1,y,s,idx+1);
- }
- if(valid_pos(x,y+1) && graph[x][y+1] == s[idx]){
- return find_sol(x,y+1,s,idx+1);
- }
- if(valid_pos(x-1,y) && graph[x-1][y] == s[idx]){
- return find_sol(x-1,y,s,idx+1);
- }
- if(valid_pos(x,y-1) && graph[x][y-1] == s[idx]){
- return find_sol(x,y-1,s,idx+1);
- }
- if(valid_pos(x+1,y+1) && graph[x+1][y+1] == s[idx]){
- return find_sol(x+1,y+1,s,idx+1);
- }
- if(valid_pos(x+1,y-1) && graph[x+1][y-1] == s[idx]){
- return find_sol(x+1,y-1,s,idx+1);
- }
- if(valid_pos(x-1,y-1) && graph[x-1][y-1] == s[idx]){
- return find_sol(x-1,y-1,s,idx+1);
- }
- if(valid_pos(x-1,y+1) && graph[x-1][y+1] == s[idx]){
- return find_sol(x-1,y+1,s,idx+1);
- }
- visited[x][y] = false;
- return "-1";
- }
- void solve(){
- for(int i=0;i<queries.size();i++){
- c = queries[i][0];
- for(int j=0;j< chars[c-'a'].size();j++){
- pair<int,int> p = chars[c-'a'][j];
- if(valid_pos(p.first,p.second)){
- string s = find_sol(p.first,p.second,queries[i],1);
- if(s!="-1"){
- cout<<queries[i]<<endl;
- cout<<p.first<<","<<p.second<<endl;
- cout<<s<<endl;
- break;
- }
- }
- }
- }
- }
- int main(){
- read();
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement