Guilty Prince Lightoj-1012

Problem link

This problem is straightforward implementation of floodfill algorithm.

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define IOS ios::sync_with_stdio(false); int dx4[] = {0, 0, 1, -1}; ///direction arrays int dy4[] = {1, -1, 0, 0}; const int maxn=25; char s[maxn][maxn]; map<pair<int,int>,int>vis; int w,h; int ans; void init(){ ans=0; vis.clear(); } void bfs(int posi,int posj){ pair<int,int>x={posi,posj}; queue<pair<int,int> > q; q.push(x); vis[x]=1; while(!q.empty()){ pair<int,int>u=q.front(); q.pop(); int x=u.first; int y=u.second; for(int i=0;i<4;i++){ int nx=x+dx4[i]; int ny=y+dy4[i]; if(nx>=0 && nx<h && ny>=0 && ny<w && s[nx][ny]=='.' && vis[mp(nx,ny)]==0){ ans++; vis[mp(nx,ny)]++; q.push(mp(nx,ny)); } } } } int tc=0; ///solution void solution(){ cin>>w>>h; int posi,posj; init(); for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ cin>>s[i][j]; if(s[i][j]=='@'){ posi=i; posj=j; } } } bfs(posi,posj); cout<< "Case "<< ++tc <<": "<< ans+1 << endl; } signed main() { IOS int t; t=1; cin>>t; while(t--){ solution(); } return 0; }

Back to Underworld Lightoj 1009 | An Easy Bfs/Dfs Problem

Problem link

Lets put a node is vampire, then all the nodes adjacent with it will be lykans.

Thats why we just need to traverse all the node by a simple bfs or dfs, by toggling nodes states( if parents is vampire then it will be lykans)

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#include<bits/stdc++.h> using namespace std; #define f0(n) for(int i=0;i<n;i++) #define pb push_back #define IOS ios::sync_with_stdio(false); const int maxn=20004; vector<int>adj[maxn]; int vis[maxn]; ///solution void init(){ f0(maxn){ adj[i].clear(); vis[i]=0; } } int bfs(int x){ queue<int>q; int va=0,ly=0; q.push(x); vis[x]=1; va++; while(!q.empty()){ int u=q.front(); q.pop(); for(auto v:adj[u]){ if(vis[v]==0){ if(vis[u]==1){ vis[v]=2; ly++; } else {vis[v]=1;va++;} q.push(v); } } } return max(va,ly); } int tc=0; void solution(){ init(); int n; cin>>n; f0(n){ int u,v; cin>>u>>v; adj[u].pb(v); adj[v].pb(u); } int ans=0; for(int i=1;i<=20000;i++){ if(vis[i]==0 && !adj[i].empty()){ ans+=bfs(i); } } cout << "Case "<<++tc << ": " << ans << endl; } signed main() { IOS int t; t=1; cin>>t; while(t--){ solution(); } return 0; }