#include<bits/stdc++.h>
using namespace std;
struct edge{
int bg;
int en;
int flow;
edge (int bg, int en, int flow) {
this -> bg = bg;
this -> en = en;
this -> flow = flow;
}
};
int height, width, n_banks;
vector<edge> edges;
vector<vector<pair<int, int> > > adj;
pair<int, int> parent[6005];
int get_in(int h, int w) {
return h * width + w;
}
int get_out(int h, int w) {
return get_in(h, w) + 3000;
}
void make_edge(int bg, int en) {
edges.push_back(edge(bg, en, 1));
adj[bg].push_back(make_pair(en, edges.size() - 1));
adj[en].push_back(make_pair(bg, edges.size() - 1));
}
bool found_path() {
queue <int> q;
for (int i = 0; i <= 6001; i++) parent[i] = make_pair(-1, -1);
q.push(6000);
parent[6000] = make_pair(0, 0);
while (!q.empty()) {
int current = q.front();
q.pop();
for (int i = 0; i < adj[current].size(); i++) {
if (parent[adj[current][i].first] != make_pair(-1, -1)) continue;
edge x = edges[adj[current][i].second];
int bg = x.bg;
int en = x.en;
if (current == bg && x.flow == 1) {
parent[en] = make_pair(bg, i);
q.push(en);
}
if (current == en && x.flow == 0) {
parent[bg] = make_pair(en, i);
q.push(bg);
}
}
}
if (parent[6001] == make_pair(-1, -1)) return 0;
else return 1;
}
int main() {
int q_;
cin >> q_;
while (q_--) {
cin >> width >> height >> n_banks;
int answer = 0;
edges.clear();
adj = vector<vector<pair<int, int> > > (6005);
for (int i = 1; i <= height; i++) {
for (int j = 1; j <= width; j++) {
make_edge(get_in(i, j), get_out(i, j));
if (i - 1 > 0) make_edge (get_out(i, j), get_in(i - 1, j));
if (j - 1 > 0) make_edge (get_out(i, j), get_in(i, j - 1));
if (i + 1 <= height) make_edge (get_out(i, j), get_in(i + 1, j));
if (j + 1 <= width) make_edge (get_out(i, j), get_in(i, j + 1));
if (i - 1 == 0 || j - 1 == 0 || i + 1 > height || j + 1 > width) make_edge (get_out(i, j), 6001);
}
}
for (int i = 0, x, y; i < n_banks; i++) {
cin >> x >> y;
make_edge(6000, get_in(y, x));
}
while (found_path()) {
answer++;
for (int i = 6001; i != 6000; i = parent[i].first) {
edges[adj[parent[i].first][parent[i].second].second].flow ^= 1;
}
}
if (answer == n_banks) cout << "possible" << '\n';
else cout << "not possible" << '\n';
}
}
Compilation message
friend.cpp: In function 'bool found_path()':
friend.cpp:41:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < adj[current].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~~~
/tmp/ccTP0w6T.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccpl0glA.o:friend.cpp:(.text.startup+0x0): first defined here
/tmp/ccTP0w6T.o: In function `main':
grader.cpp:(.text.startup+0xba): undefined reference to `findSample(int, int*, int*, int*)'
collect2: error: ld returned 1 exit status
