| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 236071 |
2020-05-31T06:56:17 Z |
kartel |
Portal (COCI17_portal) |
C++14 |
|
37 ms |
11776 KB |
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +100500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e9)
#define el '\n'
#define pii pair <int, int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
struct step{
int x, y, st;
step(int x, int y, int st) : x(x), y(y), st(st) {};
};
queue <step *> q;
int mrk[505][505];
char c[505][505];
int Left[505][505], up[505][505], Right[505][505], down[505][505], i, j, n, m, ans, found, x, y, sx, sy, ex, ey;
void get(int &x, int &y, int &st)
{
x = q.front() -> x;
y = q.front() -> y;
st = q.front() -> st;
q.pop();
}
void put(int x, int y, int st)
{
if (x == ex && y == ey) {ans = min(ans, st); return;}
q.push(new step(x, y, st));
mrk[x][y] = 1;
}
void PortalToLeft(int x, int y, int st)
{
if (Right[x][y] != y + 1 && up[x][y] != x - 1 && down[x][y] != x + 1 && !found) return;
int cx = x;
int cy = Left[x][y] + 1;
if (mrk[cx][cy]) return;
put(cx, cy, st + 1);
}
void PortalToRight(int x, int y, int st)
{
if (Left[x][y] != y - 1 && up[x][y] != x - 1 && down[x][y] != x + 1) return;
int cx = x;
int cy = Right[x][y] - 1;
if (mrk[cx][cy]) return;
put(cx, cy, st + 1);
}
void PortalToUp(int x, int y, int st)
{
if (Right[x][y] != y + 1 && Left[x][y] != y - 1 && down[x][y] != x + 1) return;
int cx = up[x][y] + 1;
int cy = y;
// cerr << x << " " << y << " " << cx << " " << cy << el;
if (mrk[cx][cy]) return;
put(cx, cy, st + 1);
}
void PortalToDown(int x, int y, int st)
{
if (Right[x][y] != y + 1 && up[x][y] != x - 1 && Left[x][y] != y - 1) return;
int cx = down[x][y] - 1;
int cy = y;
if (mrk[cx][cy]) return;
put(cx, cy, st + 1);
}
void putall(int x, int y, int st)
{
int steps[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
for (int i = 0; i < 4; i++)
{
int cx = x + steps[i][0];
int cy = y + steps[i][1];
if (cx < 1 || cy < 1 || cx > n || cy > m || mrk[cx][cy]) continue;
put(cx, cy, st + 1);
}
if (found) return;
PortalToLeft(x, y, st);
PortalToRight(x, y, st);
PortalToUp(x, y, st);
PortalToDown(x, y, st);
}
int main()
{
srand(time(0));
ios_base::sync_with_stdio(0);
iostream::sync_with_stdio(0);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
// in("input.txt");
// out("output.txt");
cin >> n >> m;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
cin >> c[i][j];
if (c[i][j] == 'C') sx = i, sy = j;
if (c[i][j] == 'F') ex = i, ey = j;
if (c[i][j] == '#') mrk[i][j] = 1;
else mrk[i][j] = 0;
}
}
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
if (c[i][j] == '#') Left[i][j] = j;
else Left[i][j] = Left[i][j - 1];
}
for (j = m; j >= 1; j--)
{
if (c[i][j] == '#') Right[i][j] = j;
else Right[i][j] = Right[i][j + 1];
}
}
for (j = 1; j <= m; j++)
{
for (i = 1; i <= n; i++)
{
if (c[i][j] == '#') up[i][j] = i;
else up[i][j] = up[i - 1][j];
}
for (i = n; i >= 1; i--)
{
if (c[i][j] == '#') down[i][j] = i;
else down[i][j] = down[i + 1][j];
}
}
ans = oo;
put(sx, sy, 0);
while (sz(q) && !found)
{
int st;
get(x, y, st);
putall(x, y, st);
}
if (ans == oo) cout << "nemoguce";
else cout << ans << el;
}
//
//110000
//1100
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
4 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
4 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
4 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
2944 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1408 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
3200 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2432 KB |
Output is correct |
| 3 |
Correct |
8 ms |
2432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
8064 KB |
Output is correct |
| 2 |
Correct |
18 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
15 ms |
5504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
10104 KB |
Output is correct |
| 2 |
Correct |
15 ms |
5632 KB |
Output is correct |
| 3 |
Correct |
20 ms |
6912 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
7296 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
11776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
