Submission #544619

#	Time	Username	Problem	Language	Result	Execution time	Memory
544619		pancankes	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	574 ms	223892 KiB

tracks

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
using namespace std;
#define int long long
const int MAXN=1e5;

// very smart solution using 0/1 BFS
// answer is just the maxinum shortest path from the top left cell
// where the weight from each adjacent cell is:
// 1 when going from different animals
// 0 when going to same animal

int n, m, dist[4000][4000], ans = 1;
// instead of storing in a grid, can speed up code by storing in vector of strings!
string snow[4000];

// standard floodfill things to include, speeds up implementation
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};

bool inside(int x, int y) {
    // since we dont care if snow[x][y] is a '.', since paths must be connected
	return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');
}

void setIO(string name="") { 
	ios_base::sync_with_stdio(0); cin.tie(0); 
	if (!name.empty()) {
		freopen((name+".in").c_str(), "r", stdin); 
		freopen((name+".out").c_str(), "w", stdout);
	}
}

int32_t main()
{
    setIO();
    cin >> n >> m;
    for (int i=0; i<n; i++) cin >> snow[i];

    // deque is just double ended queue
    deque<pair<int,int>> q;

    // search 0/1 BFS from top left grid
    q.push_back({0,0});

    // top left grid would have distance of 1 from itself
    dist[0][0]=1;

    while (!q.empty())
    {
        pair<int,int> c=q.front();
        q.pop_front();
        // answer is longest shortest distance from top left
        ans=max(ans,dist[c.first][c.second]);

        // search adjacent grid cells
        for (int i=0; i<4; i++)
        {
            int x=c.first+dx[i],y=c.second+dy[i];
            // dist also functions as a sort of visited array
            if (inside(x,y)&&dist[x][y]==0) 
            {
                // if adjacent cells are same, then they have distance of 0
                // therefore, 0/1 BFS, push to front of the queue
                if (snow[x][y]==snow[c.first][c.second])
                {
                    dist[x][y]=dist[c.first][c.second];
                    q.push_front({x,y});
                }
                else
                {
                    dist[x][y]=dist[c.first][c.second]+1;
                    q.push_back({x,y});
                }
            }
        }
    }
    cout << ans << endl;
}

Compilation message (stderr)

tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   freopen((name+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen((name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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