Submission #732376

#	Time	Username	Problem	Language	Result	Execution time	Memory
732376		vjudge1	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	0 / 100	706 ms	34664 KiB

mushrooms

#include <bits/stdc++.h>
#define sts stable_sort
#define B begin()
#define rB rbegin()
#define E end()
#define rE rend()
#define F first
#define S second
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define eb emplace_back
#define ll long long
#define ui unsigned int
#define ull unsigned long long

using namespace std;

const int MAXN = 500004;
const int MOD = 1e9 + 7;
const ll INF = 9223372036854775807LL;
const ll inf = 2147483647;
map<pair<int, int>, int> ma;

void bfs(pair<int, int> z, int r, int c, int d){

    queue<pair<pair<int, int>, int> > q;
    bool comp[r + 1][c + 1];
    comp[z.F][z.S] = 0;
    q.push({z, 0});

    while(!q.empty()){
        pair<pair<int, int>, int> x = q.front();
        q.pop();
//        cout << x.F.F << " " << x.F.S << "\n";
//        cout << r << " " << c << "\n" << "\n";
        if( x.F.F <= 0 || x.F.F > r || x.F.S <= 0 || x.F.S > c || x.S > d)continue;
//        cout << comp[x.F.F][x.F.S] << "\n";
        if(comp[x.F.F][x.F.S])continue;
        comp[x.F.F][x.F.S] = 1;
        ma[x.F]++;
//        cout << ma[x.F] << "\n";

        q.push({{x.F.F + 1, x.F.S}, x.S + 1});
        q.push({{x.F.F - 1, x.F.S}, x.S + 1});
        q.push({{x.F.F, x.F.S + 1},x.S + 1});
        q.push({{x.F.F, x.F.S - 1},x.S + 1});
        q.push({{x.F.F + 1, x.F.S - 1},x.S + 1});
        q.push({{x.F.F + 1, x.F.S + 1},x.S + 1});
        q.push({{x.F.F - 1, x.F.S - 1},x.S + 1});
        q.push({{x.F.F - 1, x.F.S + 1},x.S + 1});
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    int r, c, d, k; cin >> r >> c >> d >> k;

    vector<pair<int, int> > s;
    vector<pair<int, int> > m;

    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            char ch; cin >> ch;
            if(ch == 'S'){
                s.pb({i, j});
            }else if(ch == 'M'){
                m.pb({i, j});
            }
        }
    }

    for(int i = 0; i < s.size(); i++){
        bfs(s[i], r, c, d);
    }
    int cnt = 0;
    for(int i = 0; i < m.size(); i++){
        if(ma[m[i]] >= k)cnt++;
    }cout << cnt << "\n";

    return 0;
}
/**



**/

Compilation message (stderr)

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
mushrooms.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i = 0; i < m.size(); i++){
      |                    ~~^~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 23
• Subtask 5: 0 / 19
• Subtask 6: 0 / 21