ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 08.11.2019 19:29:09

ამოცანა: ვირუსები

მომხმარებელი: Vato

ვერდიქტი: სრული ამოხსნა

შეფასება: 100.0 ქულა







#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <utility>

int main()
{
// initialize table to false, no viruses in the beginning
    bool table[501][501] = {false};
    std::vector <std::pair <int, int>> coordinates; // stores coordinates of viruses, first - x second - y

    int n, m;
    std::cin >> n >> m; // work on n x n table with m initial virus(es)
    int x, y; // coordinates of initial virus(es)

    for (int i = 1; i <= m; ++i){ // enter coordinates m times
        std::cin >> x >> y;
        table[y][x] = true; // make virus on corresponding point
        coordinates.push_back({x,y}); // store x and y pair
    }

    int nVirus = m; // total number of all viruses
    int countMoves = 0; // moves needed to fill the table with viruses (answer)
    std::vector <std::pair <int, int>> newCoordinates; // store coordinates of new viruses

// make new viruses until the table is full
    while (nVirus != n*n){
    // start from virus 1 and on above, below, left and right
    // cells make a new virus (every virus makes 4 new virus)
        for (int i = 0; i < coordinates.size(); ++i){
            x = coordinates[i].first; // get x coordinate of virus
            y = coordinates[i].second; // get y coordinate of virus

        // if above cell is in range and there is no virus in it
            if (y+1 <= n && table[y+1][x] == false){
                table[y+1][x] = true; // make virus
                newCoordinates.push_back({x,y+1}); // store new viruses coordinates
                ++nVirus; // increment number of total viruses
            }
        // repeat same steps as above, but for below cell
            if (y-1 >= 1 && table[y-1][x] == false){
                table[y-1][x] = true;
                newCoordinates.push_back({x,y-1});
                ++nVirus;
            }
        // repeat same steps as above, but for right cell
            if (x+1 <= n && table[y][x+1] == false){
                table[y][x+1] = true;
                newCoordinates.push_back({x+1,y});
                ++nVirus;
            }
        // repeat same steps as above, but for left cell
            if (x-1 >= 1 && table[y][x-1] == false){
                table[y][x-1] = true;
                newCoordinates.push_back({x-1,y});
                ++nVirus;
            }
        }
    // coordinates are assigned to new viruses coordinates, start testing from new viruses
        coordinates = newCoordinates;
        newCoordinates.clear(); // clear storage and on next cycle store new viruses coordinates
        ++countMoves; // increment number of moves needed to fill the table
    }

    std::cout << countMoves;
}

ტესტები

შემავალი მონაცემები
5 1
2 3
გამომავალი მონაცემები
5
თქვენი პასუხი
5
ჩეკერის პასუხი
YES
შემავალი მონაცემები
5 2
1 3
5 5
გამომავალი მონაცემები
5
თქვენი პასუხი
5
ჩეკერის პასუხი
YES
შემავალი მონაცემები
6 3
1 2
1 4
1 6
გამომავალი მონაცემები
6
თქვენი პასუხი
6
ჩეკერის პასუხი
YES
შემავალი მონაცემები
6 5
2 2
2 5
4 4
6 2
6 5
გამომავალი მონაცემები
3
თქვენი პასუხი
3
ჩეკერის პასუხი
YES
შემავალი მონაცემები
7 7
1 1
2 2
3 3
4 4
5 5
6 6
7 7
გამომავალი მონაცემები
6
თქვენი პასუხი
6
ჩეკერის პასუხი
YES
შემავალი მონაცემები
50 1
3 5
გამომავალი მონაცემები
92
თქვენი პასუხი
92
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100 2
7 8
80 56
გამომავალი მონაცემები
104
თქვენი პასუხი
104
ჩეკერის პასუხი
YES
შემავალი მონაცემები
200 6
12 11
26 37
55 183
125 48
186 189
39 199
გამომავალი მონაცემები
122
თქვენი პასუხი
122
ჩეკერის პასუხი
YES
შემავალი მონაცემები
500 1
22 458
გამომავალი მონაცემები
935
თქვენი პასუხი
935
ჩეკერის პასუხი
YES
შემავალი მონაცემები
500 10
250 260
45 307
49 485
397 8
163 20
5 10
308 59
308 60
122 486
199 283
გამომავალი მონაცემები
427
თქვენი პასუხი
427
ჩეკერის პასუხი
YES