Submission #446521

#	Time	Username	Problem	Language	Result	Execution time	Memory
446521		KhoaHo	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	628 ms	130768 KiB

tracks

///KhoaHo///
#include<bits/stdc++.h>
using namespace std;
///define-zone
#define task "test"
#define vec vector
#define priq priority_queue
#define pf push_front
#define pb push_back
#define popb pop_back
#define popf pop_front
#define SZ(a) a.begin(), a.end()
#define SZZ(a, begin, end) a + begin, a + begin + end
#define fi first
#define se second
#define BIT(n) (1 << n)


///typedef-zone
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

///code-mau
template<class val> inline val gcd(val a, val b){ return (a ? gcd(b%a, a): b);}
template<class val> inline val fmul(val a, val b, val m){ if (!b) return 0; if (!(b-1)) return a; if (b%2) return (fmul(a, b/2, m)*2+a)%m; else return (fmul(a, b/2, m)*2)%m; }
template<class val> inline bool getbit(val pos, val mask) {return ((mask >> pos)&1);}
void fastio()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
}
void init()
{
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
}
const int N = 4004;
string snows[N];
int n, depth[N][N], ans = 1, m;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, -1, 0, 1};
bool check(int x, int y)
{
    return ((x >= 0)&&(x < n)&&(y < m)&&(y >= 0)&&(snows[x][y] != '.'));
}
int main()
{
    fastio();
    ///init();
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> snows[i];
    deque<ii> dq;
    depth[0][0] = 1;
    dq.pb(ii(0, 0));
    while(!dq.empty())
    {
        int x = dq.front().fi;
        int y = dq.front().se;
        dq.popf();
        ans = max(ans, depth[x][y]);
        for(int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if((check(xx, yy))&&(!depth[xx][yy]))
            {
                if(snows[x][y] == snows[xx][yy])
                {
                    depth[xx][yy] = depth[x][y];
                    dq.pf(ii(xx, yy));
                } else 
                {
                    depth[xx][yy] = depth[x][y] + 1;    
                    dq.pb(ii(xx, yy));
                }
            }
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void init()':
tracks.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen(task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen(task".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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