QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139411 | #4970. Panda Hunting Treasure Box | artcs | AC ✓ | 50ms | 20892kb | C++17 | 2.4kb | 2023-08-13 12:39:10 | 2023-08-13 12:39:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int r,c,x_s,y_s,e, temp;
int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int cost[8] = {1, 2, 3, 4, 5, 6, 7, 8};
int matriz[505][505];
vector<pair<int, int> > adj[255025];
int main()
{
cin>>r>>c>>x_s>>y_s>>e;
for(int i=0; i<r; i++)
{
for(int j=0; j<c; j++)
{
cin>>temp;
matriz[i][j] = temp;
}
}
for(int i=0; i<r; i++)
{
for(int j=0; j<c; j++)
{
if(matriz[i][j] ==0)
{
for(int k=0; k<8;k++)
{
int x = j+ dx[k];
int y = i+ dy[k];
if(x>=0 && y>=0 && x<c&&y<r)
{
//cout<<x<<"-"<<y<<endl;
int u = (i*c)+j;
int v = (y*c)+x;
//cout<<u<<" "<<v<<endl;
adj[u].push_back(pair<int,int> (v, cost[k]));
}
}
}
}
}
// for(int i =0; i<r*c;i++)
// {
// cout<<"u: "<<i<<" -> ";
// for(int j=0; j<adj[i].size();j++)
// {
// cout<<"("<<adj[i][j].first <<" "<<adj[i][j].second<<") ";
// }
// cout<<endl;
// }
//
vector<int> dist(r*c, 1000005);
x_s-=1;
y_s-=1;
int s= (x_s*c)+y_s;
dist[s] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>pq;
pq.push(pair<int,int>(0,s));
while(!pq.empty())
{
pair<int,int> front = pq.top(); pq.pop();
int d = front.first, u = front.second;
if (d>dist[u])
continue;
for(int j=0; j<(int)adj[u].size();j++)
{
pair<int,int> v = adj[u][j];
if(dist[u] + v.second < dist[v.first])
{
dist[v.first] = dist[u] + v.second;
pq.push(pair<int,int>(dist[v.first], v.first));
}
}
}
int res=0;
for(int i=0; i< r*c; i++)
{
//cout<<dist[i]<<" "<<endl;
if(dist[i]<=e)
{
int x = i/c;
int y = i%c;
res=max(res,matriz[x][y]);
}
}
cout<<res<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 9500kb
input:
5 6 1 1 55 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 1 0 10 0 1 0 0 1 9 1 0 0 0 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 9448kb
input:
5 6 1 1 56 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 1 0 10 0 1 0 0 1 9 1 0 0 0 1
output:
9
result:
ok single line: '9'
Test #3:
score: 0
Accepted
time: 1ms
memory: 9432kb
input:
5 6 1 1 57 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 1 0 10 0 1 0 0 1 9 1 0 0 0 1
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 2ms
memory: 9604kb
input:
15 15 15 15 167 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 8 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1...
output:
8
result:
ok single line: '8'
Test #5:
score: 0
Accepted
time: 3ms
memory: 9460kb
input:
15 15 15 15 168 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 8 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1...
output:
9
result:
ok single line: '9'
Test #6:
score: 0
Accepted
time: 3ms
memory: 9856kb
input:
15 15 15 15 167 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 8 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1...
output:
9
result:
ok single line: '9'
Test #7:
score: 0
Accepted
time: 50ms
memory: 18192kb
input:
500 500 95 150 10000 0 58912 45590 0 0 192022 6994 0 0 41256 153046 45791 98549 127884 244227 0 245616 77457 192184 0 129119 0 167953 0 0 37088 0 203269 218664 74293 215709 0 0 51320 146726 0 0 214633 202212 18885 197243 0 5864 231206 0 11712 188086 217785 242998 105703 189476 0 0 165813 197237 6842...
output:
246966
result:
ok single line: '246966'
Test #8:
score: 0
Accepted
time: 46ms
memory: 18252kb
input:
500 500 71 53 100 21481 159368 0 222763 181074 232082 0 0 0 227783 88926 185665 0 0 45032 216675 212780 98492 0 130666 135352 0 163811 0 117590 0 205233 223037 0 55233 117666 149034 191640 114330 184730 209724 0 65132 0 0 240862 180945 196500 223779 0 143351 216862 0 169944 207453 249638 0 0 247890 ...
output:
249725
result:
ok single line: '249725'
Test #9:
score: 0
Accepted
time: 45ms
memory: 20776kb
input:
500 500 1 1 100000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
16742
result:
ok single line: '16742'
Test #10:
score: 0
Accepted
time: 49ms
memory: 20892kb
input:
500 500 1 1 10000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1750
result:
ok single line: '1750'