QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#712960 | #8236. Snake Move | KafuuChinocpp# | WA | 281ms | 379948kb | C++14 | 3.4kb | 2024-11-05 17:38:10 | 2024-11-05 17:38:11 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int max1 = 3000, max2 = 1e5;
const int inf = 0x3f3f3f3f;
int n, m, k;
int num[max1 + 5][max1 + 5];
char Map[max1 + 5][max1 + 5];
int f[max1 + 5][max1 + 5], g[max1 + 5][max1 + 5];
struct Point
{
int x, y;
Point () {}
Point ( int __x, int __y )
{ x = __x, y = __y; }
};
vector <Point> bin[max1 * max1 + max2];
int main ()
{
int x, y, startx, starty;
scanf("%d%d%d", &n, &m, &k);
for ( int i = 1; i <= k; i ++ )
{
scanf("%d%d", &x, &y);
num[x][y] = i;
if ( i == 1 )
startx = x, starty = y;
}
for ( int i = 1; i <= n; i ++ )
scanf("%s", Map[i] + 1);
memset(g, 0x3f, sizeof(g));
f[startx][starty] = k, g[startx][starty] = 0;
bin[0].push_back(Point(startx, starty));
for ( int i = 0; i <= n * n + m; i ++ )
{
for ( auto now : bin[i] )
{
x = now.x, y = now.y;
--x;
if ( x >= 1 && Map[x][y] != '#' && g[x][y] == inf )
{
if ( num[x][y] && num[x][y] + 1 <= f[now.x][now.y] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
f[x][y] = num[x][y], g[x][y] = g[now.x][now.y] + 1 + f[now.x][now.y] - num[x][y], bin[g[x][y]].push_back(Point(x, y));
else
f[x][y] = f[now.x][now.y], g[x][y] = g[now.x][now.y] + 1, bin[g[x][y]].push_back(Point(x, y));
}
++x;
++x;
if ( x <= n && Map[x][y] != '#' && g[x][y] == inf )
{
if ( num[x][y] && num[x][y] + 1 <= f[now.x][now.y] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
f[x][y] = num[x][y], g[x][y] = g[now.x][now.y] + 1 + f[now.x][now.y] - num[x][y], bin[g[x][y]].push_back(Point(x, y));
else
f[x][y] = f[now.x][now.y], g[x][y] = g[now.x][now.y] + 1, bin[g[x][y]].push_back(Point(x, y));
}
--x;
--y;
if ( y >= 1 && Map[x][y] != '#' && g[x][y] == inf )
{
if ( num[x][y] && num[x][y] + 1 <= f[now.x][now.y] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
f[x][y] = num[x][y], g[x][y] = g[now.x][now.y] + 1 + f[now.x][now.y] - num[x][y], bin[g[x][y]].push_back(Point(x, y));
else
f[x][y] = f[now.x][now.y], g[x][y] = g[now.x][now.y] + 1, bin[g[x][y]].push_back(Point(x, y));
}
++y;
++y;
if ( y <= m && Map[x][y] != '#' && g[x][y] == inf )
{
if ( num[x][y] && num[x][y] + 1 <= f[now.x][now.y] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
f[x][y] = num[x][y], g[x][y] = g[now.x][now.y] + 1 + f[now.x][now.y] - num[x][y], bin[g[x][y]].push_back(Point(x, y));
else
f[x][y] = f[now.x][now.y], g[x][y] = g[now.x][now.y] + 1, bin[g[x][y]].push_back(Point(x, y));
}
--y;
}
}
unsigned long long ans = 0;
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= m; j ++ )
if ( g[i][j] != inf )
ans += 1uLL * g[i][j] * g[i][j];
printf("%llu\n", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 27ms
memory: 258100kb
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: 23ms
memory: 256800kb
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: 36ms
memory: 258452kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 198ms
memory: 379948kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 281ms
memory: 355756kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 50ms
memory: 270408kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 71ms
memory: 269908kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: -100
Wrong Answer
time: 174ms
memory: 379760kb
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:
49803365625415
result:
wrong answer 1st lines differ - expected: '49803365625286', found: '49803365625415'