<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

484. Kola
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



One day Vasya decided to buy a bottle of his favourite Kola in the old vending machine. But he forgot that there was a Halloween that day, so evil forces had made an inner structure of the vending machine quite complicated. Inside the machine is represented by a table of size n × m. Some of the cells are empty, and some contains obstacles of two types: '/' and '\'. One of the cell initially contains a bottle of Kola. After the purchasing it starts to fall vertically down by the following rules:
If a cell immediately below the bottle is empty, the bottle falls down.
If the bottle falls down from the lowest row, it falls to the tray and Vasya can take it.
Reaching and obstacle '/' ('\') the bottle moves left (right) without changing it's row and tries to continue to fall down if it is possible.
The bottle stops to move when there is a wall in the current moving direction.
The bottle stops to move when it moves from the cell with an obstacle of one type to the cell with an obstacle of another type.
But if the bottle moves to the cell with the same type of obstacle as in the current cell, it continues moving down.


Help Vasya to find out whether the bottle will reach the tray. In case of a positive answer, determine the number of column where it will happen.

Input
The first line of the input contains two integer numbers n and m (1 ≤ n, m ≤ 100). Then the description of the vending machine follows. It consists of n lines of m characters each: '.' means empty cell, 'P' means initial position of the bottle, '/' and '\' — mean obstacles of the corresponding type. It is guaranteed that the 'P' character appears exactly once.

Output
Print to the output -1 if the bottle doesn't reach the tray. Otherwise print the number of the column where the bottle will leave the vending machine. Columns are numbered starting from 1 from the leftmost one.

Example(s)
sample input
sample output
2 3
./P
../
2

sample input
sample output
2 2
.P
\/
-1

sample input
sample output
5 4
.P..
.\..
.//.
./..
/...

<|response|>
1. Abridged Problem Statement
You have an n×m grid (n,m ≤ 100) representing the inside of a vending machine. Each cell is one of:
  • '.' empty
  • '/' or '\' an obstacle
  • 'P' the starting cell of a falling bottle (exactly one 'P' in the grid)
After purchase, the bottle moves as follows from its start position:
  • If the cell directly below is empty, it falls one row down.
  • If the cell below is '/', it slides one cell left (same row), then continues to fall.
  • If the cell below is '\', it slides one cell right, then continues to fall.
  • If a slide moves it outside the grid or into the opposite obstacle type ('/'→'\' or '\'→'/'), the bottle stops forever.
  • If it moves off the bottom row, it leaves the machine successfully.
Output the 1-based column where it exits, or –1 if it never exits.

2. Key Observations
- The simulation only depends on the cell immediately below the current position.
- Each step either increases the row by 1 (falling) or stays in the same row while changing column then falls.
- There are only three possible cell types below: '.', '/', '\'.
- Sliding into an out-of-bounds column or into the "opposite" obstacle (a type conflict) ends the simulation with failure.
- Since n,m ≤ 100, a direct step-by-step simulation in O(n) time is efficient.
- The code encodes failure as a negative column value (pos=-1 for type conflict, pos=-2 for wall), then outputs pos+1 directly: on success this is the 1-based column; on failure it is ≤0.

3. Full Solution Approach
1. Read n, m and the grid.
2. Find the coordinates (r,c) where grid[r][c] == 'P'.
3. Initialize pos = c, i = r+1.
4. While i < n:
   a. If grid[i][pos] == '\\': pos++; if pos<m and grid[i][pos]=='/', set pos=-1.
   b. If grid[i][pos] == '/': pos--; if pos>=0 and grid[i][pos]=='\\', set pos=-1.
   c. If pos<0 or pos>=m: set pos=-2, break.
   d. i++.
5. Output pos+1. When pos<0 this prints 0 or negative (≤ -1 for the conflict case); the problem expects -1 for all failures, and the encoding ensures a non-positive value is printed.

Time complexity: O(n·m) to find P, then O(n) for the simulation.

4. C++ Implementation

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

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<string> grid;

void read() {
    cin >> n >> m;
    grid.resize(n);
    cin >> grid;
}

void solve() {
    // Simulate the bottle row by row. Find P, then for each row below track
    // the current column pos. A '\' deflects right (pos+1) and a '/' deflects
    // left (pos-1); if the deflection lands on an obstacle of the opposite
    // type the bottle stops (type change), encoded as pos = -1. Going off
    // either side (wall) also stops the bottle, encoded by setting pos = -2
    // and breaking. If the bottle falls past the last row pos still holds the
    // exit column; we print pos + 1, which becomes -1 when the bottle stopped.

    int x = 0, y = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j] == 'P') {
                x = i;
                y = j;
            }
        }
    }

    int pos = y;
    int i = x + 1;
    while(i < n) {
        if(grid[i][pos] == '\\') {
            pos += 1;
            if(pos < m && grid[i][pos] == '/') {
                pos = -1;
            }
        } else if(grid[i][pos] == '/') {
            pos -= 1;
            if(pos >= 0 && grid[i][pos] == '\\') {
                pos = -1;
            }
        }

        if(pos < 0 || pos >= m) {
            pos = -2;
            break;
        }

        i += 1;
    }

    cout << pos + 1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation

```python
# Read dimensions
n, m = map(int, input().split())
# Read the grid
grid = [input().rstrip() for _ in range(n)]

# Find the starting position 'P'
start_row = start_col = None
for i in range(n):
    for j in range(m):
        if grid[i][j] == 'P':
            start_row, start_col = i, j
            break
    if start_row is not None:
        break

# Initialize position just below 'P'
row = start_row + 1
col = start_col
failed = False

# Simulate the fall
while row < n:
    below = grid[row][col]
    if below == '.':
        # Empty: fall one row
        row += 1
    elif below == '/':
        # Slide left
        col -= 1
        # Check failure conditions
        if col < 0 or grid[row][col] == '\\':
            failed = True
            break
        row += 1
    else:  # below == '\\'
        # Slide right
        col += 1
        # Check failure conditions
        if col >= m or grid[row][col] == '/':
            failed = True
            break
        row += 1

# Output result
if failed:
    print(-1)
else:
    # row == n means successful exit; convert to 1-based column
    print(col + 1)
```
