시간 제한: 2초 / 메모리 제한: 1024MB 점수: 400점

문제 설명 N x M 크기의 격자가 주어지며, 이 격자는 얼음 또는 바위로 구성되어 있습니다. (i, j)는 위에서 i번째 행과 왼쪽에서 j번째 열에 있는 칸을 나타냅니다. 각 칸은 N개의 문자열 S1, S2, ..., SN으로 표현되며, 각 문자열의 길이는 M입니다. Si의 j번째 문자가 '.'이면 칸 (i, j)는 얼음이고, '#'이면 바위입니다. 격자의 가장자리는 모두 바위로 이루어져 있습니다. 플레이어는 처음에 (2, 2) 위치에 있으며, 이 칸은 얼음입니다. 플레이어는 상, 하, 좌, 우 중 하나의 방향을 선택하고, 그 방향으로 계속 움직이다가 바위를 만날 때까지 멈추지 않습니다. 얼음 칸을 몇 개나 지나거나 머물 수 있는지를 계산하세요.

제약 조건 3 ≤ N, M ≤ 200 Si는 '#'와 '.'로 구성된 길이 M의 문자열입니다. (1, j), (N, j), (i, 1), (i, M) 위치의 칸은 바위입니다. (2, 2) 위치의 칸은 얼음입니다.

입력 예시 1

6 6
######
#....#
#.#..#
#..#.#
#....#
######

출력 예시 1

12

입력 예시 2

21 25
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################

출력 예시 2

215

다음은 C++ 코드 예시입니다. 이 코드는 플레이어가 얼음 칸을 얼마나 많이 방문할 수 있는지를 계산합니다.

#include <iostream>
using namespace std;

char grid[210][210];
int visited[210][210][5], n, m, result = 0;

void explore(int x, int y, int dir) {
    int nx = x, ny = y;
    
    // Move in the specified direction until hitting a rock
    while (grid[nx + (dir == 1 ? -1 : dir == 2 ? 1 : 0)][ny + (dir == 3 ? -1 : dir == 4 ? 1 : 0)] == '.') {
        nx += (dir == 1 ? -1 : dir == 2 ? 1 : 0);
        ny += (dir == 3 ? -1 : dir == 4 ? 1 : 0);
        visited[nx][ny][0] = 1;
    }
    
    // Check if this direction has been explored from this point
    if (!visited[x][y][dir]) {
        visited[x][y][dir] = 1;
        
        // Explore all four directions
        for (int d = 1; d <= 4; ++d)
            explore(nx, ny, d);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> grid[i][j];
    
    // Start exploration from (2, 2)
    explore(2, 2, 1);
    explore(2, 2, 2);
    explore(2, 2, 3);
    explore(2, 2, 4);
    
    // Count all visited ice cells
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (grid[i][j] == '.' && visited[i][j][0])
                ++result;
    
    cout << result << endl;
    return 0;
}