NearSY.H
BAN USER#include <queue>
#include <vector>
#include <iostream>
using namespace std;
struct Tuple4 {
int dis, x, y, wall;
};
inline bool operator< (const Tuple4& lhs, const Tuple4& rhs){
if(lhs.dis != rhs.dis) return lhs.dis > rhs.dis;
else return lhs.wall < rhs.wall;
}
vector<pair<int, int>> solve(vector<vector<int>> maze, int sx, int sy, int dx, int dy, int w) {
int n = maze.size(), m = maze[0].size();
bool visited[n][m][w + 1];
int dis[n][m][w + 1];
int min_dis[n][m], prev[n][m][2];
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++) {
min_dis[i][j] = INT_MAX;
prev[i][j][0] = prev[i][j][1] = -1;
for(int k = 0; k <= w; k ++) {
visited[i][j][k] = false;
dis[i][j][k] = INT_MAX;
}
}
priority_queue<Tuple4> pq;
pq.push(Tuple4{0, sx, sy, w});
dis[sx][sy][w] = 0;
min_dis[sx][sy] = 0;
int ddx[] = {0, 0, -1, 1};
int ddy[] = {-1, 1, 0, 0};
while(!pq.empty()) {
Tuple4 node = pq.top();
pq.pop();
visited[node.x][node.y][node.wall] = true;
if(node.x == dx && node.y == dy) break;
for(int i = 0; i < 4; i ++) {
int nx = node.x + ddx[i];
int ny = node.y + ddy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
else if(maze[nx][ny] == 0) { // not wall
if(visited[nx][ny][node.wall])
continue;
else {
if(dis[nx][ny][node.wall] <= node.dis + 1) continue;
dis[nx][ny][node.wall] = node.dis + 1;
pq.push(Tuple4{node.dis + 1, nx, ny, node.wall});
if(dis[nx][ny][node.wall] < min_dis[nx][ny]) {
min_dis[nx][ny] = dis[nx][ny][node.wall];
prev[nx][ny][0] = node.x, prev[nx][ny][1] = node.y;
cout << nx << "," << ny << " : " << node.x << "," << node.y << endl;
}
}
} else { // wall
if(node.wall == 0) continue;
else if(visited[nx][ny][node.wall-1]) continue;
else {
if(dis[nx][ny][node.wall - 1] <= node.dis + 1) continue;
dis[nx][ny][node.wall - 1] = node.dis + 1;
pq.push(Tuple4{node.dis + 1, nx, ny, node.wall - 1});
if(dis[nx][ny][node.wall - 1] < min_dis[nx][ny]) {
min_dis[nx][ny] = dis[nx][ny][node.wall - 1];
prev[nx][ny][0] = node.x, prev[nx][ny][1] = node.y;
cout << nx << "," << ny << " : " << node.x << "," << node.y << endl;
}
}
}
}
}
vector<pair<int, int>> ret;
do {
ret.push_back(make_pair(dx, dy));
int tdx = prev[dx][dy][0];
int tdy = prev[dx][dy][1];
dx = tdx, dy = tdy;
} while(dx != -1 && dy != -1);
return ret;
}
int main() {
vector<vector<int>> maze = {
{0, 1, 1, 1, 1, 0},
{0, 1, 1, 0, 1, 0},
{0, 0, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 0}
};
vector<pair<int, int>> ans = solve(maze, 0, 0, 0, 5, 3);
for(auto n : ans) {
cout << n.first << " " << n.second << endl;
}
return 0;
}
Adapted from Dijkstra
- NearSY.H October 24, 2014I think the key point is, for each level, before any glass being fully filled, no glass under this level will get any wine in it. And in one level, once the first glass is fully filled, all glasses in the above level are all fully filled. This can be proved.
My idea is :
1. First, for each level, compute the total wine when any glass is fully filled.
2. With that, we can know when we use such amount of bottle, k-th level is fully filled, some glasses in k+1 th level is fully filled, and some glasses in k+2-th level has wine.
3. Simulate left wine.
Well I think it is easy to prove that my check is correct. But it is hard for me to prove in English. The simple idea is for 'a', 'b' (ordered), there are only two cases : .. a .. b .. a .. b .. or .. a .. a .. b .. b .. If a string as such two pairs, we replace two 'a' with the first two 'a', it still work. If we replace two 'b' with the last two 'b', it still work.
- NearSY.H October 24, 2014You can see my solution several comments above.