Solution of Light OJ 1066 - Gathering Food

/* Bismillahir Rahmanir Rahim Solution-Using BFS Apply BFS from every letter(not the last) orderly */ #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>vt[130]; int sts[130], ar[27], cnt[130], vis[130], c, ans, n, fl; void bfs(int st, int en){ queue<int>q; q.push(st); fii(ii, 0, n*n) {vis[ii]=0, cnt[ii]=0;} vis[st]=1; while(!q.empty()){ int u=q.front(); q.pop(); for(int j=0; j<vt[u].size(); j++){ int v=vt[u][j]; //if(not visited && not '#' && not getter than the next letter) if(!vis[v]&&sts[v]!=-1&&sts[v]<=en){ if(sts[v]==en){ //if(find the letter) c=cnt[u]+1; return ; } else cnt[v]=cnt[u]+1; q.push(v); vis[v]=1; } } } } int main(){ int t, cs=1, cnt, m; cin>>t; while(t--){ cin>>n; cnt=0, ans=0, m=0; fii(i, 1, n){ fii(j, 1, n){ char ch; cin>>ch; cnt++; if(ch=='.') sts[cnt]=0; else if(ch=='#') sts[cnt]=-1; else{ int x=(ch-'A')+1; m=max(m, x); // highest letter sts[cnt]=x; ar[x]=cnt; //saving the position of letters } if(i>1){ vt[cnt].push_back(cnt-n); vt[cnt-n].push_back(cnt); } if(j>1){ vt[cnt].push_back(cnt-1); vt[cnt-1].push_back(cnt); } } } /* Input End */ cout<<"Case "<<cs++<<": "; fi(1, m-1){ c=0, fl=0; bfs(ar[i], i+1); // BFS for every letter(not last) if(c==0){ // if(fail to get next letter) fl=1; break; } else ans=ans+c; } if(fl) cout<<"Impossible"<<endl; else cout<<ans<<endl; fi(0, n*n) vt[i].clear(); } return 0; }