Submission #498921

#	Time	Username	Problem	Language	Result	Execution time	Memory
498921		BBart888	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	698 ms	120908 KiB

tracks

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include<stack>
#include <set>



using namespace std;
using ll = long long;

const int INF = 1e9;
const int MAXN = 4e3+111;
const int MOD = 1e9 + 7;
const int MAXS = 250*1000+123;



int n, m;
char t[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dist[MAXN][MAXN];
int ans = 1;
pair<int, int> dd[]{ {0,1},{0,-1},{1,0},{-1,0} };


bool isIn(int i, int j)
{
    if (i < n && j < m && i >= 0 && j >= 0 && t[i][j] != '.')
        return true;
    else
        return false;
}

void bfs(int i, int j)
{
    deque<pair<int,int>> q;
    q.push_back({ i,j });
    dist[i][j] = 1;

    while (!q.empty())
    {
        pair<int,int> s = q.front();
        q.pop_front();
        ans = max(ans, dist[s.first][s.second]);
        for (pair<int, int> d : dd)
        {
            int newI = s.first + d.first;
            int newJ = s.second + d.second;
            
            if (isIn(newI, newJ) && dist[newI][newJ] == 0)
            {
                int w = (t[s.first][s.second] != t[newI][newJ]);
               
                dist[newI][newJ] = dist[s.first][s.second] + w;
                if (w == 1)
                    q.push_back({ newI,newJ });
                else
                    q.push_front({ newI,newJ });
            }

        }

    }





}


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


    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> t[i][j];



    bfs(0, 0);

    cout << ans << endl;











    return 0;
}

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