Solution of Light OJ 1012 - Guilty Prince

/* Bismillahir Rahmanir Rahim Solution-Using BFS */ #include<bits/stdc++.h> using namespace std; vector<int>vt[409]; int xx, xxx, a, b, cs=1, indx[409]; int bfs(int st){ queue<int>q; q.push(st); int cnt=0, sz, visit[409]={0}; while(!q.empty()){ xx=q.front(); q.pop(); sz=vt[xx].size(); if(!visit[xx]){ for(int i=0; i<sz; i++){ if(indx[vt[xx][i]]==1) q.push(vt[xx][i]); } visit[xx]=1; cnt++; } } for(int i=0; i<=a*b; i++)vt[i].clear(); return cnt; } int main(){ int t, st, x; string s; cin>>t; while(t--){ cin>>a>>b; x=0; for(int i=1; i<=b; i++){ x++; cin>>s; if(s[0]=='.')indx[x]=1; else if(s[0]=='#')indx[x]=0; else {st=x;indx[x]=1;} if(x-a>0){ vt[x].push_back(x-a); vt[x-a].push_back(x); } for(int j=1; j<a; j++){ x++; if(s[j]=='.')indx[x]=1; else if(s[j]=='#')indx[x]=0; else {st=x;indx[x]=1;} vt[x].push_back(x-1); vt[x-1].push_back(x); if(x-a>0){ vt[x-a].push_back(x); vt[x].push_back(x-a); } } } cout<<"Case "<<cs++<<": "<<bfs(st)<<endl; } return 0; }