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. int Cache[55][55][4];
  26. int ddx[4] = {1,-1,0,0};
  27. int ddy[4] = {0,0,1,-1};
  28.  
  29.  
  30. void Push(int o){
  31.     if (Cache[a.x][a.y][o] == -1)
  32.        return;
  33.     int x ,y;
  34.     if (o < 2){
  35.         x = a.x;
  36.         y = Cache[a.x][a.y][o];
  37.     } else {
  38.         y = a.y;
  39.         x = Cache[a.x][a.y][o];
  40.     }
  41.     int p = a.p;
  42.     while (v[x][y] == ZZ[p]) p++;
  43.     if (A[x][y][p]) return;
  44.     if (p == L){
  45.         cout << A[a.x][a.y][a.p] + 1;
  46.         exit(0);
  47.     }
  48.     A[x][y][p] = A[a.x][a.y][a.p] + 1;
  49.     Q.push( ed(x,y,p));
  50. }
  51.  
  52. int main(){
  53.     int N,M;
  54.     cin >> N >> M;
  55.     for (int i=1;i<=N;i++)
  56.         for (int j=1;j<=M;j++)
  57.                 cin >> v[i][j];
  58.  
  59.     for (int i=1;i<=N;i++){
  60.         int val = -1;
  61.         Cache[i][M][0] = -1;
  62.         for (int j=M-1;j>0;j--){
  63.             if (v[i][j] != v[i][j+1])
  64.                 val = j+1;
  65.             Cache[i][j][0] = val;
  66.         }
  67.     }
  68.  
  69.     for (int i=1;i<=N;i++){
  70.         int val = -1;
  71.         Cache[i][1][1] = -1;
  72.         for (int j=2;j<=M;j++){
  73.             if (v[i][j] != v[i][j-1])
  74.                 val = j-1;
  75.             Cache[i][j][1] = val;
  76.         }
  77.     }
  78.  
  79.     for (int i=1;i<=M;i++){
  80.         int val = -1;
  81.         Cache[N][i][2] = -1;
  82.         for (int j=N-1;j>0;j--){
  83.             if (v[j][i] != v[j+1][i])
  84.                 val = j+1;
  85.             Cache[j][i][2] = val;
  86.         }
  87.     }
  88.  
  89.     for (int i=1;i<=M;i++){
  90.         int val = -1;
  91.         Cache[1][i][3] = -1;
  92.         for (int j=2;j<=N;j++){
  93.             if (v[j][i] != v[j-1][i])
  94.                 val = j-1;
  95.             Cache[j][i][3] = val;
  96.         }
  97.     }
  98.  
  99.  
  100.    cin >> ZZ;
  101.    L = strlen(ZZ);
  102.    ZZ[L] = '*';
  103.    ZZ[++L] = 0;
  104.    int p =0;
  105.    while (v[1][1] == ZZ[p]) p++;
  106.    Q.push ( ed(1,1,p)  );
  107.    A[1][1][p] = L;
  108.    while ( true){
  109.         a = Q.front();
  110.         Q.pop();
  111.         Push(0);
  112.         Push(1);
  113.         Push(2);
  114.         Push(3);
  115.    }
  116. }
Time limit exceeded #stdin #stdout 5s 122688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xQYKLR
language:
C++ (gcc 8.3)
created:
8 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!