Submission #445091

#	Time	Username	Problem	Language	Result	Execution time	Memory
445091		Dipra_Irham	Zoo (COCI19_zoo)	C++14	0 / 110	26 ms	14156 KiB

zoo

#include "bits/stdc++.h"
#define pb(x) push_back(x)
#define fil(x, y) memset(x, y, sizeof(x))
#define ll long long
#define ff first
#define ss second
#define printp(x) x.ff << " " << x.ss
#define pii pair<int,int>
#define pll pair<long long,long long>
#define mp(x, y) make_pair(x,y)
#define inf 1073741823
#define infll 4611686018427387903
#define M 1000000007
#define db(x) cout << x << " ";
#define N 1007
#define sz size
#define sm 0.0000007
#define ins insert
#define ers erase
#define all(k) k.begin(), k.end()
#define cnt count
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;

int r, c;
int fx[] = {-1, 1, 0, 0};
int fy[] = {0, 0, 1, -1};
char adj[N][N];
int level[N][N];
bool vis[N][N];
bool vis2[N][N];
pii parent[N][N];
char ed;
void bfs(pii s)
{
    memset(vis, 0, sizeof(vis));
    memset(level, -1, sizeof(level));
    memset(parent, 0, sizeof(parent));
    vis[s.ff][s.ss] = 1;
    vis2[s.ff][s.ss] = 1;
    level[s.ff][s.ss] = 0;
    parent[s.ff][s.ss] = s;
    queue <pii> que;
    que.push(s);
    while(que.empty() != 1)
    {
        pii x = que.front();
        que.pop();
        char p = adj[x.ff][x.ss];
        for(int i = 0;i < 4;i++)
        {
            int a = x.ff + fx[i];
            int b = x.ss + fy[i];
            char next = adj[a][b];
            if(a >= 0 && a < r && b >= 0 && b < c && adj[a][b] !='*' && vis[a][b] == 0 && ((p == ed && next == p) || (p != ed)))
            {
                vis[a][b] = 1;
                vis2[a][b] = 1;
                level[a][b] = level[x.ff][x.ss] + 1;
                parent[a][b] = x;
                que.push(mp(a, b));
            }
        }
    }
}
int main()
{
    fastio;
    cin >> r >> c;
    bool g = 0, k = 0;
    for(int i = 0;i < r;i++)
    {
        for(int j = 0;j < c;j++)
        {
            cin >> adj[i][j];
        }
    }
    fil(vis2, 0);
    ed = adj[r - 1][c - 1];
    int ans = 0;
    for(int i = 0;i < r;i++)
    {
        for(int j = 0;j < c;j++)
        {
            if(adj[i][j] == ed && vis2[i][j] == 0)
            {
                bfs(mp(i, j));
                ans++;
            }
        }
    }
    fil(vis2, 0);
    for(int i = 0;i < r;i++)
    {
        for(int j = 0;j < c;j++)
        {
            if(adj[i][j] != ed && adj[i][j] != '*' && vis2[i][j] == 0)
            {
                bfs(mp(i, j));
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

zoo.cpp: In function 'int main()':
zoo.cpp:70:10: warning: unused variable 'g' [-Wunused-variable]
   70 |     bool g = 0, k = 0;
      |          ^
zoo.cpp:70:17: warning: unused variable 'k' [-Wunused-variable]
   70 |     bool g = 0, k = 0;
      |                 ^

• Subtask 1: 0 / 45
• Subtask 2: 0 / 65