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; }

Shortest Path? Toph Criterion 2021 Round 9 Explanation with code

Problem link

First of all we need to find the shortest paths from a source node S to destination node T of the given graph.

And secondly a node will be given say X and we need to find the minimum distance from node X to any node of the shortest paths.

For find that a node belongs to the shortest path or not? here is the observations,

we will run a bfs from source node and find the distances of all node from source. And again we will run another bfs from destination node and find the distance of all node from destination. If you have any doubt on bfs check the link

A node will be belong to any shortest path of the graph if distance from source + distance from destination of the node equal to the shortest path distance, in another word,

source_distance[i]+destination_distance[i] == source_distance[destination]

Now we had to find distance from any shortest path to the asking node. We can precalculate all the distances by running a bfs one more time. In this case we will push the nodes into the queue which are belong to the shortest paths and initialize the distance of these nodes as 0. This is also called Multisource bfs .

Code: