#include <stdio.h>
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi; typedef pair<ll, int> pli; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
const int MAX_N = 3e2 + 10;
struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1, T2> &p) const {
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
// Mainly for demonstration purposes, i.e. works but is overly simple
// In the real world, use sth. like boost.hash_combine
return h1 ^ h2;
}
};
int N, M, Nr[MAX_N * MAX_N];
unordered_map<pi, int, pair_hash> dis;
unordered_set<pi, pair_hash> inQ;
pi toPi(int s, int t) {
if(t == 0) return pi(s/M, s%M);
return pi(s/N, s%N);
}
int toS(int x, int y, int t) {
if(t == 0) return x*M + y;
return x*N + y;
}
bool isIn(int x, int y, int t) {
if(t == 0) return !(x<0 || y<0 || x>=N || y>=M);
return !(x<0 || y<0 || x>=M || y>=N);
}
queue<pi> Q;
void push(int x, int y, int c) {
// printf("push %d %d | %d\n", x, y, c);
if(dis[pi(x,y)] == 0 || dis[pi(x,y)] > c) {
dis[pi(x,y)] = c;
if(inQ.find(pi(x, y)) == inQ.end()) {
inQ.insert(pi(x, y));
Q.push(pi(x, y));
}
}
}
void findAns(int a, int b) {
if(a == 0 && b == 0) {
Nr[0] = -1;
return;
}
int ax, ay; tie(ax, ay) = toPi(a, 0);
int bx, by; tie(bx, by) = toPi(b, 1);
vector<int> ls[2];
for(int k=0; k<4; k++) {
int nx = ax + "1012"[k] - '1', ny = ay + "0121"[k] - '1';
if(!isIn(nx, ny, 0)) continue;
int na = toS(nx, ny, 0);
ls[0].push_back(na);
if(dis[pi(na, b)] + Nr[a] == dis[pi(a, b)]) {
Nr[a] = -1;
return findAns(na, b);
}
}
for(int k=0; k<4; k++) {
int nx = bx + "1012"[k] - '1', ny = by + "0121"[k] - '1';
if(!isIn(nx, ny, 1)) continue;
int nb = toS(nx, ny, 1);
ls[1].push_back(nb);
if(dis[pi(a, nb)] + Nr[b] == dis[pi(a, b)]) {
Nr[b] = -1;
return findAns(a, nb);
}
}
if(a == b) {
for(int na : ls[0]) for(int nb : ls[1]) {
if(dis[pi(na, nb)] + Nr[a] == dis[pi(a, b)]) {
Nr[a] = -1;
return findAns(na, nb);
}
}
}
assert(false);
}
int main() {
cin >> M >> N;
for(int i=0; i<N*M; i++) scanf("%d", &Nr[i]);
Q.push(pi(0, 0)); dis[pi(0, 0)] = Nr[0]; inQ.insert(pi(0, 0));
while(!Q.empty()) {
inQ.erase(inQ.find(Q.front()));
int a, b; tie(a, b) = Q.front(); Q.pop();
// if(a == b) printf("%d %d [%d]\n", a, b, dis[pi(a, b)]);
if(a+1 == N*M && b+1 == N*M) {
printf("%d\n", dis[pi(a, b)]);
break;
}
int ax, ay; tie(ax, ay) = toPi(a, 0);
int bx, by; tie(bx, by) = toPi(b, 1);
vector<int> ls[2];
for(int k=0; k<4; k++) {
int nx = ax + "1012"[k] - '1', ny = ay + "0121"[k] - '1';
if(!isIn(nx, ny, 0)) continue;
int na = toS(nx, ny, 0);
ls[0].push_back(na);
push(na, b, dis[pi(a,b)] + Nr[na]);
}
for(int k=0; k<4; k++) {
int nx = bx + "1012"[k] - '1', ny = by + "0121"[k] - '1';
if(!isIn(nx, ny, 1)) continue;
int nb = toS(nx, ny, 1);
ls[1].push_back(nb);
push(a, nb, dis[pi(a, b)] + Nr[nb]);
}
for(int k=0; k<2; k++) {
sort(ALL(ls[k]));
}
for(int i=0, j=0; i<SZ(ls[0]) && j<SZ(ls[1]); ) {
if(ls[0][i] == ls[1][j]) {
int v = ls[0][i];
// printf("when %d %d -> %d %d\n", a, b, v, v);
push(v, v, dis[pi(a, b)] + Nr[v]);
i++;
}else if(ls[0][i] < ls[1][j]) i++; else j++;
}
}
findAns(N*M-1, N*M-1);
for(int i=0; i<N; i++, puts("")) for(int j=0; j<M; j++) {
printf("%d ", Nr[i*M+j] == -1 ? 1 : 0);
}
return 0;
}
Compilation message
testdata.cpp: In function 'int main()':
testdata.cpp:99:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<N*M; i++) scanf("%d", &Nr[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2408 KB |
Correct |
| 2 |
Correct |
0 ms |
2408 KB |
Correct |
| 3 |
Correct |
1343 ms |
5604 KB |
Correct |
| 4 |
Execution timed out |
4000 ms |
13680 KB |
Execution timed out |
| 5 |
Halted |
0 ms |
0 KB |
- |
