Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- using namespace std;
- /* Implemented using the quick find algorithm */
- void link(vector<int> &vec, int p , int q) {
- int pid = vec[p];
- int qid = vec[q];
- for(auto i = vec.begin() ; i != vec.end() ; ++i) {
- if(*i == pid)
- *i = qid;
- }
- }
- bool connected(vector <int> vec, int p , int q) {
- return vec[p] == vec[q];
- }
- void connect(vector<int> &id, vector <int> &id1 , int p , int q ,int c, int r) {
- if(id1[p*c + q+1] == 1) link(id, p * c + q, p*c + q + 1);
- if(id1[p*c + q-1] == 1) link(id, p*c +q, p*c + q-1);
- if(id1[(p+1)*c + q] == 1) link(id, p*c +q, (p+1)*c + q);
- if(id1[(p-1)*c + q] == 1) link(id, p*c +q, (p-1)*c + q);
- }
- int main()
- {
- // Creating the map
- int r , c ;
- cin >> r >> c ;
- if (r < 1 || r > 1000 || c < 1 || c > 1000 ) return 1;
- vector <int> tab_1(r*c) , tab_2(r*c);
- vector <int> tab_3(r*c,0), tab_4(r*c,0);
- for(int i = 0 ; i < r * c; ++i) {
- tab_1[i] = i;
- tab_2[i] = i;
- }
- vector <string> map;
- for(int i = 0 ; i < r ; i++) {
- string temp;
- cin >> temp;
- if(temp.length() > c) return 1;
- map.push_back(temp);
- }
- // Receiving the queries
- int n ;
- cin >> n ;
- if(n < 0 || n > 1000) return 1;
- int r1, c1, r2, c2;
- vector < vector < int > > queries;
- for(int i = 0 ; i < n ; ++i) {
- cin >> r1 >> c1 >> r2 >> c2 ;
- if( r1 < 1 || r2 > r || c1 < 1 || c2 > c) return 1;
- vector <int> temp;
- temp.push_back(r1-1); temp.push_back(c1-1); temp.push_back(r2-1); temp.push_back(c2-1);
- queries.push_back(temp);
- }
- // Connecting the nodes
- for(int i = 0 ; i < r ; ++i) {
- for(int j = 0 ; j < c ; ++j) {
- if(map[i][j] == '0' ) {
- tab_3[i * c + j] = 1;
- connect(tab_1, tab_3, i, j, c, r);
- }
- else {
- tab_4[i*c + j ] = 1 ;
- connect(tab_2, tab_4, i, j, c, r);
- }
- }
- }
- // Displaying the results
- for(auto i = queries.begin() ; i != queries.end() ; ++i)
- {
- if(connected(tab_1, (*i)[0] * c + (*i)[1] , (*i)[2] * c + (*i)[3]) && map[(*i)[0]][(*i)[1]] == '0')
- {
- cout << "binary" << endl;
- }
- else if(connected(tab_2,(*i)[0] * c + (*i)[1] , (*i)[2] * c + (*i)[3]) && map[(*i)[0]][(*i)[1]] == '1') cout << "decimal" << endl;
- else cout << "neither" << endl;
- }
- return 0;
Add Comment
Please, Sign In to add comment