Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstring>
- #include <vector>
- #include <list>
- #include <map>
- #include <set>
- #include <deque>
- #include <queue>
- #include <stack>
- #include <bitset>
- #include <algorithm>
- #include <functional>
- #include <numeric>
- #include <utility>
- #include <sstream>
- #include <iostream>
- #include <iomanip>
- #include <cstdio>
- #include <cmath>
- #include <cstdlib>
- #include <ctime>
- #include <memory.h>
- #include <cassert>
- using namespace std;
- const int N = 22, NINF = -(1 << 30);
- char maze[N][N], res[][15] = { "IMPOSSIBLE", "SUCCESS" };
- int n, m, k, v[N][N], dist[N][N];
- int dx[] = { -1, 1, 0, 0 };
- int dy[] = { 0, 0, -1, 1 };
- struct ii {
- int x, y, s;
- ii(void) {}
- ii(int x, int y, int s) : x(x), y(y), s(s) {}
- bool operator<(const ii &o) const {
- if (s == o.s && x != o.x)
- return x > o.x;
- if (s == o.s && x == o.x)
- return y > o.y;
- return s < o.s;
- }
- };
- bool valid(int nx, int ny) {
- return nx >= 0 && ny >= 0 && nx < n && ny < m;
- }
- bool bfs(int x, int y) {
- priority_queue <ii> pq; pq.push(ii(x, y, k));
- dist[x][y] = k;
- bool taken = false;
- while (pq.size()) {
- ii co = pq.top(); pq.pop();
- int X = co.x, Y = co.y, S = co.s;
- if (S < 0) continue;
- for (int i = 0; i < 4; ++i) {
- int nx = X + dx[i], ny = Y + dy[i];
- if (valid(nx, ny) && maze[nx][ny] != '#') {
- if (maze[nx][ny] == '.') {
- if (nx == 1 && ny == 3)
- printf("that %d, %d\n", X, Y);
- if (dist[nx][ny] < dist[X][Y]) {
- dist[nx][ny] = dist[X][Y];
- pq.push(ii(nx, ny, dist[nx][ny]));
- }
- } else if (maze[nx][ny] == 's') {
- if (dist[nx][ny] < dist[X][Y] - 1 && dist[X][Y] - 1 >= 0) {
- dist[nx][ny] = dist[X][Y] - 1;
- pq.push(ii(nx, ny, dist[nx][ny]));
- }
- } else if (maze[nx][ny] == 'x') {
- if (k - dist[X][Y] <= dist[X][Y])
- return true;
- taken = true;
- //if (dist[X][Y] == 0) return false;
- if (dist[nx][ny] < dist[X][Y]) {
- dist[nx][ny] = dist[X][Y];
- pq.push(ii(nx, ny, dist[nx][ny]));
- }
- } else if (maze[nx][ny] == '@' && taken) return true;
- }
- }
- }
- return false;
- }
- int main(void) {
- //freopen("in.txt", "r", stdin);
- scanf("%d %d %d\n", &n, &m, &k);
- int sx, sy, ex, ey, cn = 0;
- for (int i = 0; i < n; i++) {
- scanf("%s", maze[i]);
- for (int j = 0; j < m && cn < 2; j++) {
- switch (maze[i][j]) {
- case '@':
- sx = i, sy = j, ++cn;
- break;
- case 'x':
- ex = i, ey = j, ++cn;
- break;
- }
- }
- }
- memset(dist, -1, sizeof dist);
- printf("%s\n", res[bfs(sx, sy)]);
- }
Advertisement
Add Comment
Please, Sign In to add comment