Submission #753754

#	Time	Username	Problem	Language	Result	Execution time	Memory
753754		tiwerlol	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	510 ms	160704 KiB

tracks

#include <iostream>
#include <map>
#include <climits>
#include <fstream>
#include <vector>
#include <stack>
#include <cmath>
#include <bitset>
#include <chrono>
#include <random>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

///ofstream cout("apm.out");
///ifstream cin("apm.in");

const int MOD = 1e9+7;

int di[4] = {-1, 1, 0, 0};
int dj[4] = {0, 0, -1, 1};

int mat[4001][4001];
int D[4001][4001];

void solve()
{
    int n, m; cin >> n >> m;

    for(int z = 0; z < n; z++)
    {
        string s; cin >> s;

        for(int x = 0; x < s.size(); x++)
        {
            if(s[x]=='.') mat[z+1][x+1] = 1;
            else if(s[x]=='R') mat[z+1][x+1] = 2;
            else mat[z+1][x+1] = 3;
            D[z+1][x+1] = 0;
        }
    }

    deque<pair<int, int>> pQ;
    pQ.push_back(make_pair(1, 1));
    D[1][1] = 1;
    int ans = 1;

    while(!pQ.empty())
    {
        int i = pQ.front().first, j = pQ.front().second;
        ans = max(ans, D[i][j]);
        pQ.pop_front();

        for(int k = 0; k < 4; k++)
        {
            int ki = di[k] + i, kj = dj[k] + j;

            if((ki>=1&&ki<=n&&kj>=1&&kj<=m) && D[ki][kj]==0 && mat[ki][kj]!=1)
            {
                D[ki][kj] = D[i][j] + (mat[i][j]!=mat[ki][kj]);
                if(mat[i][j]!=mat[ki][kj]) pQ.push_back(make_pair(ki, kj));
                else pQ.push_front(make_pair(ki, kj));
            }
        }
    }
    cout << ans;
}

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

    int tt = 1; //cin >> tt;

    while(tt--)
        solve();
}

Compilation message (stderr)

tracks.cpp: In function 'void solve()':
tracks.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int x = 0; x < s.size(); x++)
      |                        ~~^~~~~~~~~~

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