제출 #1084101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084101		hemaprakash	Tracks in the Snow (BOI13_tracks)	C++17	70.94 / 100	1032 ms	44104 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

int dir_x[] = {1, -1, 0, 0};
int dir_y[] = {0, 0, 1, -1};

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<char>> grid(n, vector<char> (m));
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> grid[i][j];
        }
    }
    if(grid[0][0] == '.' || grid[n - 1][m - 1] == '.')
    {
        cout << 0;
        return 0;
    }
    queue<pair<int, int>> fox, rabbit;
    vector<vector<bool>> visited(n, vector<bool> (m));
    if(grid[0][0] == 'F')
    {
        fox.push({0, 0});
    }
    else
    {
        rabbit.push({0, 0});
    }
    visited[0][0] = true;
    int ans = 0;
    while(fox.size() || rabbit.size())
    {
        if(fox.size())
        {
            ans++;
        }
        while(fox.size())
        {
            auto src = fox.front();
            fox.pop();
            for(int i = 0; i < 4; i++)
            {
                int x = src.first + dir_x[i], y = src.second + dir_y[i];
                if(x >= 0 && x < n && y >= 0 && y < n && visited[x][y] == false && grid[x][y] != '.')
                {
                    visited[x][y] = true;
                    if(grid[x][y] == 'F')
                    {
                        fox.push({x, y});
                    }
                    else
                    {
                        rabbit.push({x, y});
                    }
                }
            }
        }
        if(rabbit.size())
        {
            ans++;
        }
        while(rabbit.size())
        {
            auto src = rabbit.front();
            rabbit.pop();
            for(int i = 0; i < 4; i++)
            {
                int x = src.first + dir_x[i], y = src.second + dir_y[i];
                if(x >= 0 && x < n && y >= 0 && y < n && visited[x][y] == false && grid[x][y] != '.')
                {
                    visited[x][y] = true;
                    if(grid[x][y] == 'F')
                    {
                        fox.push({x, y});
                    }
                    else
                    {
                        rabbit.push({x, y});
                    }
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 25 / 30
• Subtask 2: 45.9375 / 70