fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <cstdlib>
  4. #include <string.h>
  5.  
  6. using namespace std;
  7.  
  8. typedef pair<int,int> pii;
  9.  
  10. struct ed{
  11.    int x;
  12.    int y;
  13.    int p;
  14.    ed(){}
  15.    ed(int a,int b,int c):x(a),y(b),p(c){}
  16. };
  17.  
  18. int A[55][55][10100];
  19. queue< ed > Q;
  20. char v[55][55];
  21. char ZZ[10100];
  22. int L;
  23. ed a;
  24.  
  25. pii Cache[55][55][4];
  26. int ddx[4] = {1,-1,0,0};
  27. int ddy[4] = {0,0,1,-1};
  28.  
  29. void Push(int o){
  30.     int x,y;
  31.     if (Cache[a.x][a.y][o].first!=0){
  32.         if (Cache[a.x][a.y][o].first == -1)
  33.             return ;
  34.         x = Cache[a.x][a.y][o].first;
  35.         y = Cache[a.x][a.y][o].second;
  36.     } else {
  37.     int dx = ddx[o];
  38.     int dy = ddy[o];
  39.         x = a.x;
  40.         y = a.y;        
  41.         while (v[x][y] == v[a.x][a.y]){
  42.                 x+=dx;
  43.                 y+=dy;  
  44.         }
  45.     Cache[a.x][a.y][o] = pii(x,y);
  46.         if (!v[x][y]){
  47.         Cache[a.x][a.y][o].first = -1;
  48.             return;
  49.         }
  50. }
  51.     int p = a.p;
  52.         while (v[x][y] == ZZ[p]) p++;
  53.         if (A[x][y][p]) return;
  54.         if (p == L){
  55.                 cout << A[a.x][a.y][a.p] + 1;
  56.                 exit(0);
  57.         }
  58.         A[x][y][p] = A[a.x][a.y][a.p] + 1;
  59.         Q.push( ed(x,y,p));
  60. }
  61.  
  62. int main(){
  63.     int N,M;
  64.     cin >> N >> M;
  65.     for (int i=1;i<=N;i++)
  66.         for (int j=1;j<=M;j++)
  67.                 cin >> v[i][j];
  68.    cin >> ZZ;
  69.    L = strlen(ZZ);
  70.    ZZ[L] = '*';
  71.    ZZ[++L] = 0;
  72.    int p =0;
  73.    while (v[1][1] == ZZ[p]) p++;
  74.    Q.push ( ed(1,1,p)  );
  75.    A[1][1][p] = L;
  76.    while ( true){
  77.         a = Q.front();
  78.         Q.pop();
  79.         Push(0);
  80.         Push(1);
  81.         Push(2);
  82.         Push(3);
  83.    }
  84. }
Time limit exceeded #stdin #stdout 5s 122688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zZIKHP
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!