Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <functional>
- #include <algorithm>
- #include <iostream>
- #include <stdint.h>
- #include <numeric>
- #include <utility>
- #include <sstream>
- #include <iomanip>
- #include <cstdlib>
- #include <cstring>
- #include <complex>
- #include <cassert>
- #include <climits>
- #include <cstdio>
- #include <cctype>
- #include <vector>
- #include <bitset>
- #include <string>
- #include <ctime>
- #include <deque>
- #include <stack>
- #include <cmath>
- #include <queue>
- #include <list>
- #include <map>
- #include <set>
- using namespace std;
- const int N = 22;
- char maze[N][N], res[][15] = { "IMPOSSIBLE", "SUCCESS" };
- int n, m, k, dist[N][N][444], v[N][N];
- int dx[] = { -1, 1, 0, 0 };
- int dy[] = { 0, 0, -1, 1 };
- struct ii {
- int x, y, s;
- ii(int x, int y, int s) : x(x), y(y), s(s) {}
- };
- bool valid(int nx, int ny) {
- return nx >= 0 && ny >= 0 && nx < n && ny < m;
- }
- bool bfs(int x, int y) {
- queue <ii> q; q.push(ii(x, y, k));
- dist[x][y][k] = 0;
- bool flag = false;
- int after = -1;
- while (!q.empty()) {
- ii cur = q.front(); q.pop();
- int X = cur.x, Y = cur.y, S = cur.s;
- v[X][Y] = 1;
- if (~after) S = after;
- for (int i = 0; i < 4; i++) {
- int nx = X + dx[i], ny = Y + dy[i];
- if (valid(nx, ny) && maze[nx][ny] != '#') {
- if (v[nx][ny] && !flag) continue;
- if (maze[nx][ny] == '.') {
- dist[nx][ny][S] = dist[X][Y][S] + 1;
- q.push(ii(nx, ny, S));
- } else if (maze[nx][ny] == 's' && S - 1 >= 0) {
- if (~after) --after;
- dist[nx][ny][S - 1] = dist[X][Y][S] + 1;
- q.push(ii(nx, ny, S - 1));
- } else if (maze[nx][ny] == 'x') {
- dist[nx][ny][S] = dist[X][Y][S] + 1;
- flag = true;
- after = S;
- q.push(ii(nx, ny, S));
- } else if (maze[nx][ny] == '@' && flag)
- return true;
- }
- }
- }
- return false;
- }
- int main(void) {
- //freopen("in.txt", "r", stdin);
- scanf("%d %d %d", &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;
- }
- }
- }
- puts(res[bfs(sx, sy)]);
- }
Advertisement
Add Comment
Please, Sign In to add comment