fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
  4. #define MOD 1000000007
  5. #define MOD2 998244353
  6. #define INF (1<<29)
  7. #define LINF (1LL<<60)
  8. #define EPS (1e-10)
  9. #define PI 3.1415926535897932384626433832795028
  10. #define ll long long int
  11. bool codejam = 1;
  12.  
  13. void topologicalSortUtil(int v, bool visited[], stack<int> &Stack,vector<vector<int>> adj) 
  14. {
  15.     visited[v] = true;  
  16.     vector<int>::iterator i; 
  17.     for (i = adj[v].begin(); i != adj[v].end(); ++i) 
  18.         if (!visited[*i]) 
  19.             topologicalSortUtil(*i, visited, Stack,adj); 
  20.     Stack.push(v); 
  21. } 
  22.  
  23. void topologicalSort(ll n,vector<vector<int>> adj) 
  24. { 
  25. 	ll V=n;
  26.     stack<int> Stack; 
  27.     bool *visited = new bool[V]; 
  28.     for (int i = 0; i < V; i++) 
  29.         visited[i] = false; 
  30.     for (int i = 0; i < V; i++) 
  31.         if (visited[i] == false and adj[i].size()!=0) 
  32.             topologicalSortUtil(i, visited, Stack,adj); 
  33.     while (Stack.empty() == false) 
  34.     { 
  35.         cout << (char) ('A' + Stack.top()); 
  36.         Stack.pop(); 
  37.     } 
  38. } 
  39.  
  40. void printOrder(vector<string>& words, int n, int alpha) 
  41. { 
  42. 	vector<vector<int>> adj(26,vector<int>{});
  43.     for (int i = 0; i < words.size(); i++) 
  44.     {	
  45.     	for(int j=0;j<words[i].size()-1;j++)
  46.     		adj[words[i][j]-'A'].push_back(words[i][j+1]-'A');
  47.     }
  48.     topologicalSort(n,adj); 
  49. } 
  50.  
  51. int main(){
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(0);
  54.     cout.tie(0);
  55. 	#ifndef ONLINE_JUDGE
  56. 		freopen("input.txt","r",stdin);
  57. 		freopen("output.txt","w",stdout);
  58. 	#endif
  59.  
  60. 	ll t;
  61. 	cin>>t;
  62. 	ll tc = 1;
  63. 	while(t--){
  64. 		if(codejam){
  65. 			cout<<"Case #"<<tc++<<": ";
  66. 		}
  67. 		ll r,c;
  68. 		cin>>r>>c;
  69. 		vector<vector<char>> a(r,vector<char>(c,'A'));
  70. 		map<int,map<ll,ll>> m;
  71. 		unordered_set<char> alpha;
  72. 		for(int i=0;i<r;i++){
  73. 			for(int j=0;j<c;j++){
  74. 				cin>>a[i][j];
  75. 				alpha.insert(a[i][j]);
  76. 				m[j][a[i][j]-'A']++;
  77. 			}
  78. 		}
  79. 		bool failed = false;
  80. 		for(int j=0;j<c;j++){
  81. 			for(int row = r-1;row>=0;row--){
  82. 				int count = 1;
  83. 				int count2 = 0;
  84. 				while(row>0 and a[row-1][j] == a[row][j]){
  85. 					count++;
  86. 					row--;
  87. 				}
  88. 				row = r-1;
  89. 				while(row>=0){
  90. 					if(a[row][j]==a[r-1][j])
  91. 						count2++;
  92. 					row--;
  93. 				}
  94. 				if(count != count2){
  95. 					cout<<-1<<endl;
  96. 					failed = true;
  97. 					break;
  98. 				}
  99. 			}
  100. 			if(failed)
  101. 				break;
  102. 		}
  103. 		if(!failed){
  104. 			vector<string> words;
  105. 			for(int col = 0; col<c;col++){
  106. 				string word = "";
  107. 				set<char> seen;
  108. 				for(int row=r-1;row>=0;row--){
  109. 					if(seen.find(a[row][col])==seen.end())
  110. 						word+=a[row][col];
  111. 					seen.insert(a[row][col]);
  112. 				}
  113. 				words.push_back(word);
  114. 			}
  115. 			printOrder(words,words.size(),26);
  116. 			cout<<endl;
  117. 		}
  118. 	}
  119. }
Success #stdin #stdout 0s 4400KB
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: 
Case #2: -1
Case #3: -1
Case #4: EDCBA
https://ideone.com/OXNJcW
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!