제출 #959061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959061		DaoMinh	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	599 ms	130308 KiB

tracks

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
const int maxN = 4e3 + 1;   
const int MOD = 1e9 + 7;
 
struct TCell
{
    int x, y;
};
 
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, m, deg[maxN][maxN];
char a[maxN][maxN];
 
void ReadInput()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
}
 
bool IsOut(const TCell &u)
{
    return u.x < 1 || u.x > n || u.y < 1 || u.y > m;
}
 
void Solve()
{
    int res = 1;
    deg[1][1] = 1;
    deque<TCell> Q;
    Q.push_front({1, 1});
    while (!Q.empty())
    {
        TCell u = Q.front();
        Q.pop_front();
        res = max(res, deg[u.x][u.y]);
        for (int i = 0; i < 4; i++)
        {
            TCell v = {u.x + dx[i], u.y + dy[i]};
            if (!IsOut(v) && a[v.x][v.y] != '.' && deg[v.x][v.y] == 0)
            {
                if (a[v.x][v.y] == a[u.x][u.y])
                {
                    deg[v.x][v.y] = deg[u.x][u.y];
                    Q.push_front(v);
                }
                else
                {
                    deg[v.x][v.y] = deg[u.x][u.y] + 1;
                    Q.push_back(v);
                }
            }
        }
    }
    cout << res;
}
 
#define task ""
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    int T = 1;
    //cin >> T;
    while (T--)
    {
        ReadInput();
        Solve();
    }
}

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