QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#139411#4970. Panda Hunting Treasure BoxartcsAC ✓50ms20892kbC++172.4kb2023-08-13 12:39:102023-08-13 12:39:12

Judging History

你现在查看的是最新测评结果

  • [2023-08-13 12:39:12]
  • 评测
  • 测评结果:AC
  • 用时:50ms
  • 内存:20892kb
  • [2023-08-13 12:39:10]
  • 提交

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'