fork download
  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
stdin
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
Case #1: 
Case #2: -1
Case #3: -1
Case #4: EDCBA