fork download
copy 
  1. /** Author : Aishwarya Mittal **/
  2.  
  3. /********   All Required Header Files ********/
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6.  
  7. // SCAN
  8. #define scd(t) scanf("%d",&t)
  9. #define scd2(a,b) scanf("%d %d",&a, &b);
  10. #define scd3(a,b,c) scanf("%d %d %d",&a, &b,&c);
  11. #define sclld(t) scanf("%lld",&t)
  12.  
  13. // PRINT
  14. #define prd(n) printf("%d",n)
  15. #define prl(n) printf("%lld",n)
  16. #define prdl(n) printf("%d\n",n)
  17. #define prll(n) printf("%lld\n",n)
  18. #define ps printf(" ")
  19. #define pn printf("\n")
  20. #define rep(i, j) for(int i=0;i<j;i++)
  21. #define rup(i,a,b) for(int i=a;i<=b;i++)
  22. #define rdn(i,a,b) for(int i=a;i>=b;i--)
  23. typedef pair<int, int> pii;
  24. typedef vector<int> vi;
  25. typedef vector<string> vs;
  26. typedef vector<pii> vii;
  27. typedef vector<vi> vvi;
  28. typedef long long int ll;
  29. #define pb push_back
  30. #define mp make_pair
  31.  
  32.  
  33. bool topoSort(int s, vi G[], stack<int>& stk, bool vis[], bool rec[]){
  34.     if(!vis[s]){
  35.         vis[s]=true;
  36.         rec[s]=true;
  37.         for(auto v: G[s]){
  38.             if(!vis[v] && topoSort(v,G,stk,vis,rec))
  39.                 return true;
  40.             else if(rec[v])
  41.                 return true;
  42.         }
  43.         stk.push(s);
  44.     }
  45.     rec[s]=false;
  46.     return false;
  47. }
  48. void solve(){
  49. 	int r,c;
  50. 	int size = 26;
  51.     vi G[26];
  52.     bool vis[26]={false};
  53.     bool present[26] = {false};
  54.     bool rec[26]={false};
  55.     stack<int> stk;
  56.     scd2(r,c);
  57.     string A[r];
  58.     rep(i,r)
  59.         cin>>A[i];    
  60.  
  61.     // mark if a char is present 
  62.     rep(i,r){
  63.         rep(j,c){
  64.             present[A[i][j]-'A'] = true;
  65.         }
  66.     }
  67.  
  68.     // form the graph using adjacency list for edges
  69.     rep(j,c){
  70.         rdn(i,r-2,0){
  71.             if(A[i+1][j]!=A[i][j])
  72.                 G[A[i+1][j]-'A'].pb(A[i][j]-'A');
  73.         }
  74.     }
  75.  
  76. 	// remove duplicte edges from graph
  77.     rep(i,26){
  78.         if(G[i].size()>0){
  79.             std::sort(G[i].begin(), G[i].end()); 
  80.             auto ip = std::unique(G[i].begin(), G[i].end()); 
  81.             G[i].resize(std::distance(G[i].begin(), ip)); 
  82.         }
  83.     }
  84.  
  85.     // flag to denote non stable wall i.e. cycle present in graph
  86.     // find order of blocks using topological sorting
  87.     bool flag = true;
  88.     rep(i,26){
  89.         if(!vis[i] && present[i]){
  90.             if(topoSort(i,G,stk,vis,rec)){
  91.                 flag = false;
  92.                 break; 
  93.             }
  94.         }     
  95.     }
  96.  
  97.     if(flag){
  98.         while(!stk.empty()){
  99.         cout<<((char)(stk.top()+'A'));
  100.         stk.pop();
  101.         }
  102.     }
  103.     else
  104.         cout<<"-1";
  105.  
  106.     cout<<"\n";
  107. }
  108.  
  109. int main()
  110. {
  111. 	int t;
  112. 	scd(t);
  113. 	rup(tc,1,t)
  114. 	{
  115. 		printf("Case #%d: ",tc); 
  116.         solve();
  117. 	}
  118.     return 0;
  119. }
Success #stdin #stdout 0s 4324KB
comments (?)
stdin
copy 
4
4 6
ZOAAMM
ZOAOMM
ZOOOOM
ZZZZOM
4 4
XXOO
XFFO
XFXO
XXXO
5 3
XXX
XPX
XXX
XJX
XXX
3 10
AAABBCCDDE
AABBCCDDEE
AABBCCDDEE
stdout
copy 
Case #1: ZOMA
Case #2: -1
Case #3: -1
Case #4: EDCBA
https://ideone.com/rHxaJa
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!