Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <algorithm>
- using namespace std;
- int main()
- {
- int n, m, pi, pj, ki, kj;
- cin >> n >> m;
- char mat[n][m];
- for(int i = 0; i< n; i++){
- for(int j = 0; j < m; j++){
- cin >> mat[i][j];
- if (mat[i][j] == 'P'){
- pi = i;
- pj = j;
- }
- if (mat[i][j] == 'K'){
- ki = i;
- kj = j;
- }
- }
- }
- bool visited[3][n][m];
- for(int i = 0; i < 3; i++){
- for(int j = 0; j < n; j++){
- for(int z = 0; z < m; z++){
- visited[i][j][z] = false;
- }
- }
- }
- visited[0][pi][pj] = true;
- int di[] = {1, -1, 0, 0, 2, -2, 0, 0, 3, -3, 0, 0};
- int dj[] = {0, 0, 1, -1, 0, 0, 2, -2, 0, 0, 3, -3};
- queue<int> q;
- q.push(pi);
- q.push(pj);
- q.push(0);
- q.push(1);
- // cout << pi << " " << pj << endl;
- while (!q.empty()){
- int ci = q.front();
- q.pop();
- int cj = q.front();
- q.pop();
- int dist = q.front();
- q.pop();
- int cekor = q.front();
- q.pop();
- // cout << ci << " " << cj << endl;
- // cout << mat[ci][cj] << " " << endl;
- if(mat[ci][cj] == 'K'){
- cout << dist << endl;
- return 0;
- }
- if (cekor == 1){
- for (int i = 0; i < 4; i++){
- int ti = ci + di[i];
- int tj = cj + dj[i];
- if (ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#' and !visited[0][ti][tj]){
- visited[0][ti][tj] = true;
- q.push(ti);
- q.push(tj);
- q.push(dist + 1);
- q.push(2);
- }
- }
- }
- else if (cekor == 2){
- for (int i = 0; i < 4; i++){
- int ti = ci + di[i];
- int tj = cj + dj[i];
- if (ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#'){
- ti = ci + di[i + 4];
- tj = cj + dj[i + 4];
- if (ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#' and !visited[1][ti][tj]){
- visited[1][ti][tj] = true;
- q.push(ti);
- q.push(tj);
- q.push(dist+1);
- q.push(3);
- }
- }
- }
- }else if (cekor == 3){
- for (int i = 0; i < 4; i++){
- int ti = ci + di[i];
- int tj = cj + dj[i];
- if (ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#'){
- ti = ci + di[i + 4];
- tj = cj + dj[i + 4];
- if (ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#'){
- ti = ci + di[i + 8];
- tj = cj + dj[i + 8];
- if (ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '#' and !visited[2][ti][tj]){
- visited[2][ti][tj] = true;
- q.push(ti);
- q.push(tj);
- q.push(dist+1);
- q.push(1);
- }
- }
- }
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement