# 13940 ~ 13942 - Plankton's clever plan (with more reward)
>author: Utin
###### tags: `BFS`

---

## Brief
See the code below

## Solution 0

#include <bits/stdc++.h>

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

int ans = INT_MAX, ax = INT_MAX, ay = INT_MAX;
int M, N, port = 0, Port[1005][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] == '@')
                    End[0] = i, End[1] = j;
                if (Map[i][j] == '#')
                    Grid[i][j] = true;
                if (Map[i][j] == 'O')
                    Port[port][0] = i, Port[port++][1] = j;
            }
        }
    }

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

    while (process.size()) {

        State curr = process.front();
        process.pop();

        if (curr.step > ans) break;

        if (Map[curr.x][curr.y] == 'P') {
            ans = curr.step;
            if (curr.x < ax) ax = curr.x, ay = curr.y;
            else if (curr.x == ax && curr.y < ay) ax = curr.x, ay = curr.y;
        }

        if (Map[curr.x][curr.y] == 'O') {
            for (int p = 0; p < port; p++) {
                if (!Grid[Port[p][0]][Port[p][1]]) {
                    process.push(State(Port[p][0], Port[p][1], curr.step + 1));
                    Grid[Port[p][0]][Port[p][1]] = true;
                }
            }
        }

        for (int i = 0; i < 4; i++) {
            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 << ans << '\n' << ax << ' ' << ay << '\n';

}

// By Utin

## Reference