---
# System prepended metadata

title: 13923 - Plankton's clever plan
tags: [BFS]

---

# 13923 - Plankton's clever plan
>author: Utin
###### tags: `BFS`

---

## Brief
See the code below

## Solution 0

```cpp=
#include <bits/stdc++.h>

struct State {
    int x, y, step;
    State(int x, int y, int s) : x(x), y(y), step(s) {}
};

int M, N, Start[2], End[2], Mov[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char Map[1005][1005];
bool Grid[1005][1005];

std::queue<State> process;

int main() {

    // get input
    std::cin >> M >> N;
    for (int i = 0; i <= M + 1; i++) {
        for (int j = 0; j <= N + 1; j++) {
            if (i == 0 || j == 0 || i == M + 1 || j == N + 1) {
                Map[i][j] = '#';
                Grid[i][j] = true;
            }
            else {
                std::cin >> Map[i][j];
                if (Map[i][j] == 'P') 
                    Start[0] = i, Start[1] = j;
                if (Map[i][j] == '@')
                    End[0] = i, End[1] = j;
                if (Map[i][j] == '#')
                    Grid[i][j] = true;
            }
        }
    }

    // BFS
    process.push(State(Start[0], Start[1], 0));
    Grid[Start[0]][Start[1]] = true;

    while (process.size()) {
        
        State curr = process.front();
        process.pop();

        for (int i = 0; i < 4; i++) {
            if (Map[curr.x + Mov[i][0]][curr.y + Mov[i][1]] == '@') {
                std::cout << curr.step + 1 << '\n';
                return 0;
            }
            if (!Grid[curr.x + Mov[i][0]][curr.y + Mov[i][1]]) {
                process.push(State(curr.x + Mov[i][0], curr.y + Mov[i][1], curr.step + 1));
                Grid[curr.x + Mov[i][0]][curr.y + Mov[i][1]] = true;
            }
        }

    }

    std::cout << -1 << '\n';

}

// By Utin
```

## Reference