Submission #749174

#	Time	Username	Problem	Language	Result	Execution time	Memory
749174		nonono	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	854 ms	119248 KiB

tracks

#include "bits/stdc++.h"
using namespace std;

const int mxN = 4e3 + 10;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int n, m;
char a[mxN][mxN];
int dp[mxN][mxN];

bool inside(int x, int y){
    return (x >= 1) && (x <= n) && (y >= 1) && (y <= m);
}

signed main(){

    #define name "test"
    if(fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            cin >> a[i][j];
        }
    }
    
    int res = 1;
    deque<pair<int, int>> dq;
    dq.push_front({1, 1});
    dp[1][1] = 1;
    
    while(!dq.empty()){
        pair<int, int> c = dq.front();
        dq.pop_front();
        
        res = max(res, dp[c.first][c.second]);
        
        for(int i = 0; i < 4; i ++){
            int x = c.first + dx[i];
            int y = c.second + dy[i];
              
            if(inside(x, y) && a[x][y] == a[c.first][c.second] && dp[x][y] == 0){
                dq.push_front({x, y});
                dp[x][y] = dp[c.first][c.second];
            } else if(inside(x, y) && a[x][y] != '.' && dp[x][y] == 0){
                dq.push_back({x, y});
                dp[x][y] = dp[c.first][c.second] + 1;
            }
        }
    }
    
    cout << res << "\n";
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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