Submission #877581

#	Time	Username	Problem	Language	Result	Execution time	Memory
877581		asli_bg	Tracks in the Snow (BOI13_tracks)	C++11	0 / 100	806 ms	153776 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define MOD 1000000007

const int MAXN=4e3+1;

bool vis[MAXN][MAXN];

int grid[MAXN][MAXN];

int h,w;

int xyon[5]={1,0,-1,0};
int yyon[5]={0,-1,0,1};

int say=0;

bool isvalid(int x,int y){
    if(x>=h or x<0 or y>=w or y<0) return false;
    return true;
}

int d[MAXN][MAXN];

void bfs(int x,int y){
    queue<pii> q;
    q.push({x,y});
    vis[x][y]=true;
    d[x][y]=0;

    while(!q.empty()){
        auto el=q.front();
        q.pop();

        for(int i=0;i<4;i++){
            int newx=el.fi+xyon[i];
            int newy=el.se+yyon[i];

            if(isvalid(newx,newy) and !vis[newx][newy]){
                vis[newx][newy]=true;
                q.push({newx,newy});
                d[newx][newy]+=d[el.fi][el.se]+(grid[newx][newy]==grid[el.fi][el.se]?0:1);
                //cout<<"distance of "<<grid[newx][newy]<<" is: "<<d[newx][newy]<<endl;
            }

        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); 

    cin>>h>>w;

    map<char,int> anim;
    anim['F']=1;
    anim['R']=0;
    anim['.']=-1;

    int all_steps=0;

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            char c;
            cin>>c;
            grid[i][j]=anim[c];
        }
    }

    bfs(0,0);
    cout<<d[h-1][w-1]<<endl;

}
    

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:68:9: warning: unused variable 'all_steps' [-Wunused-variable]
   68 |     int all_steps=0;
      |         ^~~~~~~~~

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