# Appreciation

/*
 * Problem :: 2151 / 거울 설치
 *
 * Kind :: BFS (Revisit)
 *
 * Insight
 * - Logic 은 위의 코드와 동일하다
 *   + 다만, Queue 가 아닌 Deque 으로 구현하면
 *     가장 먼저 반대쪽 문에 도달하는 빛이
 *     지나온 거울의 수가 최소인 빛으로 만들 수 있다
 *     # 거울을 지나치지 않는 빛을 Deque 앞쪽에, 거울을 지나친 빛을 Deque 뒤쪽에 넣고
 *       Deque 앞에서 하나씩 꺼내쓰는 것으로
 *       항상 현재 다루고 있는 빛이 최소로 거울을 지나쳐온 빛들이 되게끔 한다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>
#include <deque>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N;
struct Point { int y, x; };
struct Light { Point p; int d; };
int dy[4] = {+1, 0, 0, -1};
int dx[4] = {0, +1, -1, 0};
#define INF 987654321

// Set up : Functions Declaration
bool isValid(int y, int x);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N;
    char board[N][N];
    vector<Point> door;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> board[i][j];
            if (board[i][j] == '#') {
                door.push_back({i, j});
            }
        }
    }

    // Process
    deque<Light> que;
    bool isVisited[N][N][4];
    memset(isVisited, false, sizeof(isVisited));
    int isCount[N][N][4];
    memset(isCount, -1, sizeof(isCount));

    Point sd = door.front(); /* Start Door, 한쪽 문, 빛의 시작 위치 */
    Point ed = door.back(); /* End Door, 반대쪽 문, 빛의 최종 목적지 */
    for (int i=0; i<4; i++) { /* 모든방향(상하좌우)에 빛을 쏴줌 */
        que.push_front({sd, i});
        isVisited[sd.y][sd.x][i] = true;
        isCount[sd.y][sd.x][i] = 0;
    }

    int ans = INF;
    while (not(que.empty())) {
        Light cl = que.front(); que.pop_front();
        int cy = cl.p.y; /* 현재 빛의 y 좌표 */
        int cx = cl.p.x; /* 현재 빛의 x 좌표 */
        int cd = cl.d; /* 현재 빛의 방향 */
        int cnt = isCount[cy][cx][cd]; /* 현재 빛이 지나온 거울의 개수 */

        /* 반대쪽 문에 처음 도착한 빛이 최소한으로 거울을 지나온 빛임 */
        if (cy == ed.y && cx == ed.x) {
            ans = cnt;
            break;
        }

        /* 빛이 가던 방향 그대로 현재 위치를 지나가는 경우 */
        int ny = cy + dy[cd];
        int nx = cx + dx[cd];
        if (isValid(ny, nx)) { /* 가고자 하는 다음 좌표가 유효하고 */
            if (board[ny][nx] != '*') { /* 빛이 통과할 수 없는 벽이 아니며 */
                /* 방문하지 않았거나
                 * 현재 빛이 이전에 지나친 빛의 지나온 거울의 개수보다 적다면 */
                if (not(isVisited[ny][nx][cd]) || isCount[ny][nx][cd] > cnt) {
                    /* 방문 처리 및 정보 갱신 */
                    isVisited[ny][nx][cd] = true;
                    isCount[ny][nx][cd] = cnt;
                    que.push_front({{ny, nx}, cd}); /* Deque 의 앞에 넣어줌 */
                }
            }
        }

        /* 현재 위치에 거울을 놓을 수 있어서, 거울을 놓아 빛이 방향을 90도 꺾은 경우 */
        if (board[cy][cx] == '!') {
            for (int i=0; i<4; i++) {
                    /* 현재 빛의 진행방향과 그 반대 방향은 넘어감 */
                if (i == cd || 3-i == cd) continue;
                ny = cy + dy[i];
                nx = cx + dx[i];
                if (isValid(ny, nx)) { /* 가고자 하는 다음 좌표가 유효하고 */
                    if (board[ny][nx] != '*') { /* 빛이 통과할 수 없는 벽이 아니며 */
                        /* 방문하지 않았거나
                         * 현재 빛이 이전에 지나친 빛의 지나온 거울의 개수-1 보다 적다면 */
                        if (not(isVisited[ny][nx][i]) || isCount[ny][nx][i] > cnt+1) {
                            /* 방문 처리 및 정보 갱신 */
                            isVisited[ny][nx][i] = true;
                            isCount[ny][nx][i] = cnt+1;
                            que.push_back({{ny, nx}, i}); /* Deque 의 뒤에 넣어줌 */
                        }
                    }
                }
            }
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
bool isValid(int y, int x)
/* 유효한 좌표면 true 를 반환, 그 외 false 를 반환 */
{
    return y >= 0 && y < N && x >= 0 && x < N;
}