LIGHT OJ – 1012 SOLUTION

PROBLEM LINK:

LIGHT OJ-1012 (GUILTY PRINCE)

SOLUTION:

//To learn about pair<int,int> , please go to pair c++
//To learn about memset(), please go to memset()

#include <bits/stdc++.h>
#define _clear(a) memset(a,0,sizeof(a))
#define pii pair<int,int>
using namespace std;
int main()
{
int t;
cin>>t;
for(int n = 0; n<t; n++)
{
int col,row,source_x,source_y;
cin>>col>>row;
char arr[row][col];
char a;
for(int i = 0; i<row; i++) {
for(int j = 0; j<col; j++) {
cin>>a;
if(a==’@’) {
source_x = i;
source_y = j;
}
arr[i][j] = a;
}
}
bool visited[row][col];
int DX[] = {-1,1,0,0};
int DY[] = {0,0,-1,1};
int counter = 1;
queue <pii>q;
_clear(visited);
visited[source_x][source_y] = true;
q.push(pii(source_x,source_y));
while(!q.empty()) {
pii top = q.front();
q.pop();

    for(int k = 0; k<4; k++) {
int f = top.first + DX[k];
int s = top.second + DY[k];
if(arr[f][s] == ‘#’)continue;
else if((f>=0&&f<row)&&  (s>=0&&s<col)&&(!visited[f][s])&&arr[f][s] == ‘.’) {
visited[f][s] = true;
counter++;
q.push(pii(f,s));
}
}

}
cout<<“Case “<<n+1<<“: “<< counter<<endl;
}
}

LIGHT OJ 1009 SOLUTION

PROBLEM LINK:

LIGHTOJ 1009 BACK TO UNDERWORLD

SOLUTION:

#include <bits/stdc++.h>
#define _clear(a) memset(a,0,sizeof(a))
using namespace std;
vector <int> edge[20004];
int level[20004];
bool visited[20004],used[20004];
int parent[20004];
int T,m,a,b,cnt,source;
int vam[20004];
int lyn[20004];
int bfs() {
queue <int> q;
visited = true;
int cnt1=0,cnt2=0,u,v;
_clear(vam);
_clear(lyn);
cnt = 0;
q.push(source);
vam = 1;
visited=1;
while(!q.empty()) {
u = q.front();
q.pop();
for(int i = 0; i<edge[u].size(); i++) {
v = edge[u][i];
if(!visited[v]) {
if(!vam[u])
vam[v] = 1;
if(!lyn[u])
lyn[v] = 1;
visited[v]=1;
q.push(v);
}
}
}
for(int j = 0; j<20004; j++) {
if(vam[j]==1)
cnt1++;

}
for(int j = 0; j<20004; j++) {
if(lyn[j]==1)
cnt2++;
}
if(cnt1>cnt2) {
cnt = cnt1;
return cnt;
} else {
cnt = cnt2;
return cnt;
}

}
int main() {

cin>>T;
for(int i = 1; i<=T; i++) {
cin>>m;
memset(used,0,sizeof(used));
for(int i=0;i<20004;i++)edge[i].clear();
_clear(visited);
for(int j = 0; j<m; j++) {
cin>>a>>b;
edge[a].push_back(b);
edge[b].push_back(a);
used[a]=used[b]=1;
}
int ans=0;
for(int j=0; j<20004; j++) {
if(used[j] && !visited[j]){
source=j;
bfs();
ans+=cnt;
}
}
cout<<“Case “<<i<<“: “<<ans<<“\n”;
}

}