Advertisement
Josif_tepe

Untitled

Apr 6th, 2022
949
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.16 KB | None
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <math.h>
  5. #include <vector>
  6. #include <queue>
  7. using namespace std;
  8. char mat[105][105];
  9. bool visited[105][105][1 << 8];
  10. int main()
  11. {
  12.     int n, m;
  13.     cin >> n >> m;
  14.     int si, sj;
  15.     int ei, ej;
  16.     for(int i = 0; i < n; i++) {
  17.         for(int j = 0; j < m; j++) {
  18.             cin >> mat[i][j];
  19.             if(mat[i][j] == 'P') { // pocetok
  20.                 si = i;
  21.                 sj = j;
  22.             }
  23.             if(mat[i][j] == 'K') {
  24.                 ei = i;
  25.                 ej = j;
  26.             }
  27.         }
  28.     }
  29.     for(int i = 0; i < n; i++) {
  30.         for(int j = 0; j < m; j++) {
  31.             for(int mask = 0; mask < (1 << 8); mask++) {
  32.                 visited[i][j][mask] = false;
  33.             }
  34.         }
  35.     }
  36.     queue<int> q;
  37.     q.push(si);
  38.     q.push(sj);
  39.     q.push(0); // koi klucevi do sega sme gi zemale
  40.     q.push(0); // kolku cekori do tuka sme pominale
  41.     visited[si][sj][0] = true;
  42.     int di[] = {-1, 1, 0, 0};
  43.     int dj[] = {0, 0, -1, 1};
  44.     while(!q.empty()) {
  45.         int ci = q.front();
  46.         q.pop();
  47.         int cj = q.front();
  48.         q.pop();
  49.         int bitmask = q.front();
  50.         q.pop();
  51.         int cekor = q.front();
  52.         q.pop();
  53.         if(mat[ci][cj] == 'K') {
  54.             cout << cekor << endl;
  55.             return 0;
  56.         }
  57.         for(int i = 0; i < 4; i++) {
  58.             int ti = ci + di[i];
  59.             int tj = cj + dj[i];
  60.             if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#') {
  61.                 if(mat[ti][tj] >= 'a' and mat[ti][tj] <= 'h') {
  62.                     int bukva = mat[ti][tj] - 'a';
  63.                     int zemeno = bitmask | (1 << bukva);
  64.                     if(!visited[ti][tj][zemeno]) {
  65.                         visited[ti][tj][zemeno] = true;
  66.                         q.push(ti);
  67.                         q.push(tj);
  68.                         q.push(zemeno);
  69.                         q.push(cekor + 1);
  70.                     }
  71.                 }
  72.                 else if(mat[ti][tj] >= 'A' and mat[ti][tj] <= 'H') {
  73.                     int bukva = mat[ti][tj] - 'A';
  74.                     if(bitmask & (1 << bukva)) {
  75.                         if(!visited[ti][tj][bitmask]) {
  76.                             q.push(ti);
  77.                             q.push(tj);
  78.                             q.push(bitmask);
  79.                             q.push(cekor + 1);
  80.                             visited[ti][tj][bitmask] = true;
  81.                         }
  82.                     }
  83.                 }
  84.                 else {
  85.                     if(!visited[ti][tj][bitmask]) {
  86.                         visited[ti][tj][bitmask] = true;
  87.                         q.push(ti);
  88.                         q.push(tj);
  89.                         q.push(bitmask);
  90.                         q.push(cekor + 1);
  91.                     }
  92.                 }
  93.                
  94.             }
  95.         }
  96.     }
  97.     cout << "Ne moze da se stigne do kraj" << endl;
  98.     return 0;
  99. }
  100. /*
  101.  
  102. P..A
  103. ..#K
  104. ...#
  105. a...
  106.  
  107.  
  108. 10 10
  109. P.....d..f
  110. ####F#D###
  111. ..........
  112. ......h..b
  113. .#####H###
  114. .#....a...
  115. .#.###A###
  116. .#.#...c..
  117. .#.#.####C
  118. .B.#.#...K
  119.  
  120.  */
  121.  
Advertisement
RAW Paste Data Copied
Advertisement