relogios.cpp

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

int l,c,k;
int m[110][110], vis[110][110];
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};

bool valid(int x, int y){

    if(x >=0 and x <l and y >=0 and y<c) return true;
    return false;
}

int diferenca(int i, int j){
	if(i<j) return j-i;
	else return k-i+j;
}

int dijkstra(){

    priority_queue< iii, vector<iii>, greater<iii>> q;
    q.push({0,{0,0}});

    while(!q.empty()){

        int t = q.top().first, x = q.top().second.first, y = q.top().second.second;
        q.pop();

        if(x == l -1 and y == c-1) return t;

        if(vis[x][y] != -1) continue;
        vis[x][y] = 1;

        for(int i= 0; i<4; i++){

            int novox = x + dx[i], novoy = y + dy[i];
            if(!valid(novox, novoy)) continue;
            if(vis[novox][novoy] != -1) continue;


            if(m[novox][novoy] == -1) q.push({t + 1, {novox, novoy}});

            else{

                if(m[x][y] != -1 and diferenca(m[x][y], m[novox][novoy]) > 1) continue;
                else{

                    int add = diferenca( (t % k), m[novox][novoy]);
                    q.push({t + add, {novox, novoy}});
                } 
            }
        }
    }

    return -1;
}

int main(){

    cin >> l >> c >> k;

    for(int i=0; i<l; i++) for(int j = 0; j<c; j++) cin >> m[i][j];
    memset(vis, -1,sizeof(vis));

    cout << dijkstra() << endl;
    return 0;
}