QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#636354 | #8236. Snake Move | LurkInShadow | WA | 1002ms | 93992kb | C++17 | 3.1kb | 2024-10-12 23:33:09 | 2024-10-12 23:33:09 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define ls u << 1
#define rs u << 1 | 1
#define ff first
#define ss second
#define pb push_back
#define p_q priority_queue
#define INF 0x7FFFFFFF
#define INFF 9223372036854775807
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
using namespace std;
using TIII = tuple<int,int,int>;
using PII = pair<int, int>;
using ULL = unsigned long long;
using ld = long double;
const int MOD = 998244353;
const double eps = 1e-9;
const int N = 3010;
int n,m,k;
char g[N][N];
int dist[N][N];
int snake[N][N]; // 第i节蛇身在{x,y}处,走到的代价是snake[x][y]
bool vis[N][N];
int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};
PII se;
void solve()
{
cin >> n >> m >> k;
p_q<TIII,vector<TIII>,greater<TIII>> pq;
memset(dist,0x3f,sizeof dist);
for(int i = 0;i < k;i ++)
{
int x,y;
cin >> x >> y;
x --,y --;
if(i == 0)
{
pq.emplace(0,x,y);
dist[x][y] = 0;
continue;
}
if(i == 1)
{
se.ff = x;
se.ss = y;
}
snake[x][y] = k - i - 1;
}
for(int i = 0;i < n;i ++)
{
for(int j = 0;j < m;j ++)
{
cin >> g[i][j];
}
}
while(!pq.empty())
{
auto t = pq.top();
pq.pop();
int d = get<0>(t),x = get<1>(t),y = get<2>(t);
if(vis[x][y]) continue;
vis[x][y] = true;
for(int i = 0;i < 4;i ++)
{
int nx = x + dx[i],ny = y + dy[i];
if(nx < 0 || nx > n || ny < 0 || ny > m) continue;
if(g[nx][ny] == '#') continue;
int nd = max(d + 1,snake[nx][ny] + 1);
if(dist[nx][ny] > nd)
{
dist[nx][ny] = nd;
if(nx == se.ff && ny == se.ss)
{
dist[nx][ny] = min(nd,k - 1);
}
pq.emplace(dist[nx][ny],nx,ny);
}
}
// cout << x << ' ' << y << ' ' << dist[x][y] << '\n';
}
int ans = 0;
for(int i = 0;i < n;i ++)
{
for(int j = 0;j < m;j ++)
{
if(dist[i][j] >= INF / 2) continue;
// cout << dist[i][j] << ' ';
ans += (dist[i][j] * dist[i][j]);
}
// cout << '\n';
}
cout << ans << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
/*
/\7 ∠_/
/ │ / /
│ Z _,< / /`ヽ
│ ヽ / 〉
Y ` / /
イ● 、 ● ⊂⊃〈 /
() へ | \〈
>ー 、_ ィ │ //
/ へ / ノ<| \\
ヽ_ノ (_/ │//
7 |/
>―r ̄ ̄`ー―_
*/
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 77520kb
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: 79336kb
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: 0ms
memory: 79600kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: -100
Wrong Answer
time: 1002ms
memory: 93992kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141931664769
result:
wrong answer 1st lines differ - expected: '35141960580077', found: '35141931664769'