QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#590065 | #8236. Snake Move | SLF666 | WA | 860ms | 82024kb | C++17 | 1.7kb | 2024-09-25 21:22:41 | 2024-09-25 21:22:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define endl "\n"
const int N = 5e5 + 5, inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
struct node{
int x,y,dis;
bool operator < (const node &slf)const{
return dis > slf.dis;
}
};
int nx[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
void solve(){
int n,m,k;
cin>>n>>m>>k;
vector<vector<int>>vis(n+1, vector<int>(m+1));
vector<vector<char>>g(n+1, vector<char>(m+1));
vector<vector<int>>dis(n+1, vector<int>(m+1, inf));
vector<vector<bool>>book(n+1, vector<bool>(m+1));
priority_queue<node>q;
for(int i=1,x,y;i<=k;i++){
cin>>x>>y;
vis[x][y] = i;
if(i == 1){
q.push({x, y, 0});
dis[x][y] = 0;
}
}
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
cin>>g[i][j];
}
while(!q.empty()){
auto [x, y, d] = q.top();
q.pop();
if(book[x][y])continue;
book[x][y] = 1;
for(int i=0;i<4;i++){
int dx = x + nx[i][0];
int dy = y + nx[i][1];
if(dx < 0 || dx > n || dy < 0 || dy > m)continue;
if(g[dx][dy] == '#' || book[dx][dy])continue;
if(vis[dx][dy] > 1){
int t = max(k - vis[dx][dy], d) + 1;
if(dis[dx][dy] > t){
q.push({dx, dy, t});
dis[dx][dy] = t;
}
}
else if(dis[dx][dy] > d + 1){
q.push({dx, dy, d + 1});
dis[dx][dy] = d + 1;
}
}
}
ull ans = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
// cout<<dis[i][j]<<" ";
if(dis[i][j] == inf)continue;
ans += (ull)dis[i][j] * (ull)dis[i][j];
}//cout<<endl;
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3564kb
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: 3780kb
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: 3628kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 860ms
memory: 82024kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: -100
Wrong Answer
time: 727ms
memory: 81680kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17470812522819
result:
wrong answer 1st lines differ - expected: '17464052497724', found: '17470812522819'