#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 0 1 0 1 0 1 0
// 1 0 1 0 1 0 1
// 0 1 0 0 0 1 0
// 1 0 1 0 1 0 1

struct Point {
  int x;
  int y;
  Point(int x, int y) : x(x), y(y) {};
};

bool InMap(const vector<vector<int>>& map, const Point& p) {
  return (p.x >= 0 && p.x < map.size() && p.y >= 0 && p.y < map[0].size());
}

// Check if a graph is bipartite
bool IsBipartite (const vector<vector<int>>& map) {

  vector<vector<bool>> visited_map(map.size(), vector<bool> (map[0].size(), false));

  vector<vector<int>> neighbors_map{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

  queue<Point> q_points;
  Point first_point(0, 0);
  q_points.push(first_point);
  visited_map[0][0] = true;

  while (!q_points.empty()) {
    Point current = q_points.front();
    q_points.pop();

    for (int i = 0; i < 4; ++i) {
      Point neighbor(current.x + neighbors_map[i][0], current.y + neighbors_map[i][1]);
      if (InMap(map, neighbor) && !visited_map[neighbor.x][neighbor.y]) {
        if (map[neighbor.x][neighbor.y] != map[current.x][current.y]) {
          q_points.push(neighbor);
          visited_map[neighbor.x][neighbor.y] = true;
        }
        else
          return false;
      }
    }

  }

  return true;
}


int main() {

  vector<vector<int>> map{{0, 1, 0, 1, 0, 1, 0},
                          {1, 0, 1, 0, 1, 0, 1},
                          {0, 1, 0, 0, 0, 1, 0},
                          {1, 0, 1, 0, 1, 0, 1}};

  cout << IsBipartite(map) << endl;


  return 0;
}