My solution differs from the official. It passes task 1 and 10 only.
Differences:
- I denote edges as set of three edges.
So the edge weight is the value of the next grass field + 3*t
Then obviously to get to field (n-1, n-1) (0 -indexed) we must check all fields with Manhattan distance of 2 (1 or 2)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector vi;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define FOR(i, x, y) for (int i = x; i < y ; i ++)
void IO(string s){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
int n, t;
const int MAX_N = 101;
int val[MAX_N][MAX_N];
vii adj[MAX_N][MAX_N];
ll dist[MAX_N][MAX_N];
int visited[MAX_N][MAX_N];
//generates all possible groups of 3 edges that start at vertex (i,j)
void generate(int i, int j){
vii a = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
FOR(x, 0, 4){
int y = 3 - x;
for(auto pr : a){
int new_i = i + pr.first*x;
int new_j =j + pr.second*y;
if (new_i >= 0 && new_j >= 0 && new_i < n && new_j < n){
adj[i][j].PB(MP(new_i, new_j));
}
}
}
for(auto pr : a){
int new_i = i + pr.first;
int new_j =j + pr.second;
if (new_i >= 0 && new_j >= 0 && new_i < n && new_j < n){
adj[i][j].PB(MP(new_i, new_j));
}
}
}
ll dijkstra(){
FOR(i, 0, MAX_N){
FOR(j, 0, MAX_N){
dist[i][j] = LLONG_MAX;
visited[i][j] = 0;
}
}
priority_queue<pair<ll, ii>> q;
q.push(MP(0, MP(0, 0)));
dist[0][0] = 0;
while(!q.empty()){
ii a = q.top().second;
q.pop();
if (visited[a.first][a.second]){
continue;
}
visited[a.first][a.second] = 1;
for(auto next : adj[a.first][a.second]){
ll new_dist = dist[a.first][a.second] + val[next.first][next.second] + 3*t;
if (new_dist < dist[next.first][next.second]){
dist[next.first][next.second] = new_dist;
q.push(MP(-new_dist, next));
}
}
}
dist[n - 1][n - 1] = min(dist[n - 1][n - 1], t + dist[n - 1][n - 2]);
dist[n - 1][n - 1] = min(dist[n - 1][n - 1], t + dist[n - 2][n - 1]);
FOR(i, 0, 3){
int j = 2 - i;
dist[n - 1][n - 1] = min(dist[n - 1][n - 1], dist[n - 1 -i][n- 1 - j] + 2 *t);
}
return dist[n - 1][n - 1];
}
int main(){
IO("visitfj");
cin >> n >> t;
FOR(i, 0, n){
FOR(j, 0, n){
cin >> val[i][j];
generate(i, j);
}
}
cout << dijkstra() << '\n';
}