Advertisement
Guest User

Untitled

a guest
Nov 21st, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.22 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3.  
  4. using namespace std;
  5. int64_t **matrix(int64_t **a, int64_t **b,int n)
  6. {
  7.     int64_t **c = new int64_t*[n];
  8.     for(int i=0;i<n;i++)
  9.     {
  10.         c[i] = new int64_t[n];
  11.     }
  12.     for(int i=0; i < n; i++){
  13.         for(int j=0; j < n; j++){
  14.             c[i][j]=0;
  15.             for(int k=0; k < n; k++)
  16.             {
  17.                 c[i][j]+=a[i][k]*b[k][j];
  18.             }
  19.         }
  20.     }
  21.     return c;
  22.  
  23. }
  24.  
  25. int64_t  **binpow (int64_t **a, int k,int n) {
  26.     if (k == 0)
  27.     {
  28.         int64_t **answer = new int64_t*[n];
  29.         for(int i=0;i<n;i++)
  30.         {
  31.             answer[i] = new int64_t[n];
  32.         }
  33.         for(int i=0;i<n;i++)
  34.         {
  35.             for(int j=0;j<n;j++)
  36.             {
  37.                 if(i==j) answer[i][j]=1;
  38.                 else answer[i][j] = 0;
  39.             }
  40.         }
  41.         return answer;
  42.     }
  43.     if (k % 2 == 1)
  44.     {
  45.         return matrix(binpow(a, k-1,n), a,n);
  46.     }
  47.     else {
  48.         int64_t **b = binpow (a, k/2,n);
  49.         return matrix(b,b,n);
  50.     }
  51. }
  52.  
  53.  
  54.  
  55.  
  56.  
  57. int main()
  58. {
  59.     int n, m, k;
  60.     int startx, endx;
  61.     cin >> n >> m >> k;
  62.     int *pole = new int [n*m];
  63.     for(int j=0;j<n*m;j++)
  64.     {
  65.         char x;
  66.         cin >> x;
  67.         if(x == '+') pole[j] = -1;
  68.         else if(x == '.') pole[j] = 1;
  69.         else if(x == '#'){startx = j; pole[j] = 1;}
  70.         else if(x == '@'){endx = j; pole[j] = 1;}
  71.     }
  72.     int64_t **kek = new int64_t *[n*m];
  73.     for(int i=0;i<n*m;i++)
  74.     {
  75.         kek[i] = new int64_t [m*n];
  76.     }
  77.     for(int i=0;i<n*m;i++)
  78.     {
  79.         for(int j=i;j<n*m;j++)
  80.         {
  81.             if(((abs(i-j) == 1 && (((j+1) % m )!= 0) && (((i+1) % m )!=0)) ||((i-j) == 1 && (((i+1) % m)==0)) ||((j-i==1) && (((j+1) % m)==0)) ||((abs(i-j)==m))) && pole[i] == 1 && pole[j] == 1 )
  82.             {
  83.                 kek[i][j] = 1;
  84.                 kek[j][i] = 1;
  85.             }
  86.             else{
  87.                 kek[i][j] = 0;
  88.                 kek[j][i] = 0;
  89.             }
  90.         }
  91.     }
  92.     /*for(int i=0;i<n*m;i++)
  93.     {
  94.         for(int j=0;j<n*m;j++){
  95.             cout << kek[i][j] << " ";
  96.         }
  97.         cout << endl;
  98.     } */
  99.     int64_t **answer  = binpow(kek,k,n*m);
  100.     cout << answer[startx][endx] << " ";
  101.  
  102.  
  103.     return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement