Solution of Light OJ 1337 - The Crystal Maze

/* Bismillahir Rahmanir Rahim Solution-Using DFS Firstly visit all nodes and keeping answer in every node **Input section is long not the main code** */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fii(i, n, m) for(int i=n; i<=m; i++) using namespace std; vector<int>vc, vt[250009]; int vis[250009], sts[250009], n, m, q, cnt, x, y, ans; void dfs(int at){ if(vis[at]) return ; else{ vis[at]=1; if(sts[at]==1) cnt++; // if(node=='C') vc.push_back(at); //storing-the nodes in a chain for(int z=0; z<vt[at].size(); z++){ int v=vt[at][z]; if(!vis[v] && sts[v]!=-1){ dfs(v); } } } } int main(){ int t, cs=1, ans[250009]; cin>>t; while(t--){ cnt=0; cin>>n>>m>>q; fii(i, 1, n){ char ch; cin>>ch; cnt++; if(ch=='#') sts[cnt]=-1; else if(ch=='.') sts[cnt]=0; else sts[cnt]=1; if(i!=1){ vt[cnt].push_back(cnt-m); vt[cnt-m].push_back(cnt); } fii(j, 2, m){ cin>>ch; cnt++; if(ch=='#') sts[cnt]=-1; else if(ch=='.') sts[cnt]=0; else sts[cnt]=1; vt[cnt].push_back(cnt-1); vt[cnt-1].push_back(cnt); if(i!=1){ vt[cnt].push_back(cnt-m); vt[cnt-m].push_back(cnt); } } } fi(0, n*m) vis[i]=0; fi(1, n*m){ cnt=0; if(sts[i]!=-1) dfs(i); // if(node!='#') //cnt=total Crystal; ans[every node in this chain]=cnt; for(int zz=0; zz<vc.size(); zz++) ans[vc[zz]]=cnt; vc.clear(); } cout<<"Case "<<cs++<<":"<<endl; fi(1, q){ cin>>x>>y; x=(x-1)*m+y; // one dimensional position not (x, y) cout<<ans[x]<<endl; } fi(0, n*m) vt[i].clear(); } return 0; }