Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2019
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.57 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement