Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <cstdlib>
- #include <cstring>
- #include <cassert>
- #include <cstdio>
- #include <vector>
- #include <cctype>
- #include <string>
- #include <ctime>
- #include <cmath>
- #include <set>
- #include <map>
- typedef long double LD;
- typedef long long LL;
- using namespace std;
- #define sz(A) (A).size()
- #define mp make_pair
- #define pb push_back
- #define N 15
- #define M 17
- #define x first
- #define y second
- char plan[M][M];
- int cnt[M][M], cnt_next[M][M], dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
- void read() {
- for (int i = 1; i <= N; i++)
- for (int j = 1; j <= N; j++)
- cin >> plan[i][j];
- for (int i = 1; i <= N; i++)
- for (int j = 1; j <= N; j++)
- cin >> cnt[i][j];
- }
- void end_move() {
- cout << endl;
- int trash;
- cin >> trash;
- }
- int dist[M][M], qx[M * M], qy[M * M], l, r;
- pair<int, int> from[M][M];
- void push(int x, int y) {
- qx[r] = x, qy[r++] = y;
- }
- void print_move(int x1, int y1, int x2, int y2) {
- cout << x1 - 1 << " " << y1 - 1 << " ";
- for (int i = 0; i < 4; i++)
- if (x1 + dx[i] == x2 && y1 + dy[i] == y2) {
- cout << i << " ";
- break;
- }
- cout << cnt[x1][y1] << endl;
- }
- void bfs(int x, int y) {
- l = r = 0;
- push(x, y);
- while (l < r) {
- int now_x = qx[l], now_y = qy[l++];
- for (int i = 0; i < 4; i++) {
- int to_x = now_x + dx[i], to_y = now_y + dy[i];
- if (plan[to_x][to_y] == '#')
- continue;
- if (dist[to_x][to_y])
- continue;
- if ( (cnt[to_x][to_y] < 0 && -cnt[to_x][to_y] > cnt[x][y]) || (cnt_next[to_x][to_y] < 0 && -cnt_next[to_x][to_y] > cnt[x][y]) )
- continue;
- if (cnt[to_x][to_y] < 0 || plan[to_x][to_y] == '#' || plan[to_x][to_y] == 'H') {
- if (now_x == x && now_y == y) {
- print_move(x, y, to_x, to_y);
- return;
- }
- while (from[now_x][now_y] != mp(x, y)) {
- int prev_x = now_x;
- now_x = from[prev_x][now_y].x;
- now_y = from[prev_x][now_y].y;
- }
- print_move(x, y, now_x, now_y);
- return;
- }
- dist[to_x][to_y] = dist[now_x][now_y] + 1;
- from[to_x][to_y] = mp(now_x, now_y);
- push(to_x, to_y);
- }
- }
- }
- int main() {
- read();
- for (int i = 1; i <= N; i++)
- for (int j = 1; j <= N; j++)
- for (int k = 0; k < 4; k++)
- if (cnt[i + dx[k] ][j + dy[k] ] < 0)
- cnt_next[i][j] -= cnt[ i + dx[k] ][ j + dy[k] ];
- for (int i = 1; i <= N; i++)
- for (int j = 1; j <= N; j++) {
- if (cnt[i][j] > 0) {
- bfs(i, j);
- }
- }
- end_move();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement