QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#847900 | #8236. Snake Move | liderek | WA | 636ms | 153364kb | C++14 | 2.6kb | 2025-01-08 12:55:40 | 2025-01-08 12:55:41 |
Judging History
answer
#include <iostream>
#include <limits>
#include <queue>
#define int long long
using namespace std;
constexpr const int inf = numeric_limits<int>::max();
int n, m, k;
bool grid[3001][3001];
int snake_pos[3001][3001];
int dist[3001][3001];
pair<int, int> snake[100001];
struct node
{
int x, y, d;
node(int x, int y, int d) : x(x), y(y), d(d)
{
}
};
void bfs()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
dist[i][j] = inf;
}
}
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
queue<node> q;
int current_idle_d = 0;
q.push(node(snake[0].first, snake[0].second, 0));
dist[snake[0].first][snake[0].second] = 0;
while (!q.empty())
{
node cur = q.front();
q.pop();
if (cur.d > current_idle_d)
{
current_idle_d = cur.d;
q.push(node(snake[0].first, snake[0].second, cur.d));
}
// left, right, up, down
for (int i = 0; i < 4; i++)
{
int new_x = cur.x + dx[i];
int new_y = cur.y + dy[i];
int new_d = cur.d + 1;
if (new_x < 0 || new_x >= n)
continue;
if (new_y < 0 || new_y >= m)
continue;
if (dist[new_x][new_y] != inf)
continue;
if (grid[new_x][new_y])
continue;
if (snake_pos[new_x][new_y] != -1)
{
if (snake_pos[new_x][new_y] > new_d)
continue;
}
dist[new_x][new_y] = min(new_d, dist[new_x][new_y]);
q.push(node(new_x, new_y, new_d));
}
}
}
int32_t main()
{
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
snake_pos[i][j] = -1;
}
}
for (int i = 0; i < k; i++)
{
int x, y;
cin >> x >> y;
snake[i] = {x - 1, y - 1};
snake_pos[x - 1][y - 1] = k - i;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
char c;
cin >> c;
grid[i][j] = (c == '#');
}
}
bfs();
unsigned int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (dist[i][j] == inf)
continue;
ans += dist[i][j] * dist[i][j];
// cout << dist[i][j] << ' ';
}
// cout << endl;
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7908kb
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....
output:
293
result:
ok single line: '293'
Test #2:
score: 0
Accepted
time: 0ms
memory: 9744kb
input:
2 2 4 1 1 1 2 2 2 2 1 .. ..
output:
14
result:
ok single line: '14'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7712kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 484ms
memory: 153172kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 607ms
memory: 148552kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 279ms
memory: 153032kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 259ms
memory: 153292kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 491ms
memory: 148556kb
input:
2900 3000 10 2883 1758 2883 1759 2883 1760 2883 1761 2883 1762 2884 1762 2884 1763 2883 1763 2882 1763 2882 1764 ........................................................#............................#........................................................................................................
output:
49803365625286
result:
ok single line: '49803365625286'
Test #9:
score: 0
Accepted
time: 636ms
memory: 153364kb
input:
3000 3000 10 2015 1932 2015 1931 2015 1930 2015 1929 2016 1929 2017 1929 2018 1929 2018 1928 2018 1927 2017 1927 #...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......
output:
22509095749285
result:
ok single line: '22509095749285'
Test #10:
score: -100
Wrong Answer
time: 278ms
memory: 152980kb
input:
3000 2900 10 326 1781 325 1781 325 1782 325 1783 325 1784 324 1784 324 1783 323 1783 323 1782 324 1782 ##.#....#.###.######..#.#.....##.#.##..####.####.##..#..#.###.#####....##.#.##.#..###..##.###.##.#####.###..##.#..##..##.#..##.#.#.##...##..#.##.##........#..#..###.##.###.####.#..########.##.....#...
output:
41915
result:
wrong answer 1st lines differ - expected: '40571', found: '41915'