Submission #49732

#	Time	Username	Problem	Language	Result	Execution time	Memory
49732		imeimi2000	Dangerous Skating (JOI16_skating)	C++17	100 / 100	529 ms	22160 KiB

skating

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

struct node {
    int x, y, d;
    bool operator<(const node &p) const {
        return d > p.d;
    }
};

const int inf = 1e8;
int r, c;
char grid[1000][1001];
int close[4][1000][1000];
int dist[1000][1000];
priority_queue<node> pq;
void pushDist(int x, int y, int d) {
    if (0 <= x && x < r && 0 <= y && y < c) {
        if (grid[x][y] == '#') return;
        if (dist[x][y] <= d) return;
        dist[x][y] = d;
        pq.push({ x, y, d });
    }
}
const int gox[4] = { -1, 0, 1, 0 };
const int goy[4] = { 0, -1, 0, 1 };
int main() {
	scanf("%d%d", &r, &c);
	int sx, sy, ex, ey;
	for (int i = 0; i < r; ++i) {
        scanf("%s", grid[i]);
        for (int j = 0; j < c; ++j) {
            dist[i][j] = inf;
        }
	}
	scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
	--sx; --sy;
	--ex; --ey;
	for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (grid[i][j] != '#') {
                close[0][i][j] = close[0][i - 1][j] + 1;
                close[1][i][j] = close[1][i][j - 1] + 1;
            }
            else close[0][i][j] = close[1][i][j] = -1;
        }
	}
	for (int i = r; i--; ) {
        for (int j = c; j--; ) {
            if (grid[i][j] != '#') {
                close[2][i][j] = close[2][i + 1][j] + 1;
                close[3][i][j] = close[3][i][j + 1] + 1;
            }
            else close[2][i][j] = close[3][i][j] = -1;
        }
	}
	pushDist(sx, sy, 0);
	while (!pq.empty()) {
        node tp = pq.top();
        pq.pop();
        int x = tp.x, y = tp.y, d = tp.d;
        if (x == ex && y == ey) {
            printf("%d\n", d);
            return 0;
        }
        if (dist[x][y] != d) continue;
        for (int i = 0; i < 4; ++i) {
            int l = close[i][x][y];
            pushDist(x + gox[i] * l, y + goy[i] * l, d + 1);
            pushDist(x + gox[i], y + goy[i], d + 2);
        }
	}
	printf("-1\n");
	return 0;
}

Compilation message (stderr)

skating.cpp: In function 'int main()':
skating.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &r, &c);
  ~~~~~^~~~~~~~~~~~~~~~
skating.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", grid[i]);
         ~~~~~^~~~~~~~~~~~~~~
skating.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 65 / 65
• Subtask 3: 22 / 22