Guest User

Untitled

a guest
Jun 21st, 2018
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.47 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. /* Implemented using the quick find algorithm */
  8.  
  9. void link(vector<int> &vec, int p , int q) {
  10. int pid = vec[p];
  11. int qid = vec[q];
  12. for(auto i = vec.begin() ; i != vec.end() ; ++i) {
  13. if(*i == pid)
  14. *i = qid;
  15. }
  16. }
  17.  
  18. bool connected(vector <int> vec, int p , int q) {
  19. return vec[p] == vec[q];
  20. }
  21.  
  22. void connect(vector<int> &id, vector <int> &id1 , int p , int q ,int c, int r) {
  23. if(id1[p*c + q+1] == 1) link(id, p * c + q, p*c + q + 1);
  24. if(id1[p*c + q-1] == 1) link(id, p*c +q, p*c + q-1);
  25. if(id1[(p+1)*c + q] == 1) link(id, p*c +q, (p+1)*c + q);
  26. if(id1[(p-1)*c + q] == 1) link(id, p*c +q, (p-1)*c + q);
  27. }
  28.  
  29. int main()
  30. {
  31.  
  32. // Creating the map
  33. int r , c ;
  34. cin >> r >> c ;
  35. if (r < 1 || r > 1000 || c < 1 || c > 1000 ) return 1;
  36. vector <int> tab_1(r*c) , tab_2(r*c);
  37. vector <int> tab_3(r*c,0), tab_4(r*c,0);
  38.  
  39. for(int i = 0 ; i < r * c; ++i) {
  40. tab_1[i] = i;
  41. tab_2[i] = i;
  42. }
  43.  
  44. vector <string> map;
  45. for(int i = 0 ; i < r ; i++) {
  46. string temp;
  47. cin >> temp;
  48. if(temp.length() > c) return 1;
  49. map.push_back(temp);
  50. }
  51.  
  52. // Receiving the queries
  53. int n ;
  54. cin >> n ;
  55. if(n < 0 || n > 1000) return 1;
  56.  
  57. int r1, c1, r2, c2;
  58. vector < vector < int > > queries;
  59. for(int i = 0 ; i < n ; ++i) {
  60.  
  61. cin >> r1 >> c1 >> r2 >> c2 ;
  62. if( r1 < 1 || r2 > r || c1 < 1 || c2 > c) return 1;
  63. vector <int> temp;
  64. temp.push_back(r1-1); temp.push_back(c1-1); temp.push_back(r2-1); temp.push_back(c2-1);
  65. queries.push_back(temp);
  66. }
  67.  
  68.  
  69. // Connecting the nodes
  70.  
  71. for(int i = 0 ; i < r ; ++i) {
  72. for(int j = 0 ; j < c ; ++j) {
  73.  
  74. if(map[i][j] == '0' ) {
  75. tab_3[i * c + j] = 1;
  76. connect(tab_1, tab_3, i, j, c, r);
  77. }
  78. else {
  79. tab_4[i*c + j ] = 1 ;
  80. connect(tab_2, tab_4, i, j, c, r);
  81. }
  82. }
  83. }
  84.  
  85. // Displaying the results
  86. for(auto i = queries.begin() ; i != queries.end() ; ++i)
  87. {
  88. if(connected(tab_1, (*i)[0] * c + (*i)[1] , (*i)[2] * c + (*i)[3]) && map[(*i)[0]][(*i)[1]] == '0')
  89. {
  90. cout << "binary" << endl;
  91. }
  92. else if(connected(tab_2,(*i)[0] * c + (*i)[1] , (*i)[2] * c + (*i)[3]) && map[(*i)[0]][(*i)[1]] == '1') cout << "decimal" << endl;
  93. else cout << "neither" << endl;
  94. }
  95.  
  96. return 0;
Add Comment
Please, Sign In to add comment