제출 #1331595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1331595		algorubik	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	2098 ms	83836 KiB

tracks

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m;
    cin>>n>>m;

    vector<string> g(n);
    for(int i=0;i<n;i++) cin>>g[i];

    vector<vector<int>> dp(n,vector<int>(m,-1));
    queue<pair<int,int>> q;

    dp[0][0]=1;
    q.push({0,0});

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

    while(!q.empty()){
        auto [x,y]=q.front();
        q.pop();

        for(int k=0;k<4;k++){
            int nx=x+dx[k];
            int ny=y+dy[k];

            if(nx<0||ny<0||nx>=n||ny>=m) continue;
            if(g[nx][ny]=='.') continue;

            int val=dp[x][y]+(g[nx][ny]!=g[x][y]);

            if(val>dp[nx][ny]){
                dp[nx][ny]=val;
                q.push({nx,ny});
            }
        }
    }

    cout<<dp[n-1][m-1]<<"\n";
}

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