# Untitled

unknown
plain_text
a year ago
7.9 kB
3
Indexable
Never
```#include <iostream>
#include <fstream>
#define MIN 99999999
using namespace std;

int n, g;
int arr[21][21];
int TG[10][21][21];
int visited[21][21];
int dR[4] = { -1, 0, 1, 0 };
int dC[4] = { 0, 1, 0, -1 };
int visitedV[10];

ifstream input("input.txt");
fstream output;

typedef struct Point {
int x, y;
};

Point G[10];

typedef struct Queue {
int front, rear;
Point data[10001];
};

void init(Queue& Q) {
Q.front = Q.rear = -1;
}

void push(Queue& Q, Point value) {
Q.rear++;
Q.data[Q.rear] = value;
}

Point top(Queue& Q) {
Point temp;
Q.front++;
temp = Q.data[Q.front];
Q.front--;
return temp;
}

void pop(Queue& Q) {
Q.front++;
}

bool empty(Queue& Q) {
if (Q.front == Q.rear)
return true;
return false;
}

Queue Q;

void BFS(int index, Point P) {
init(Q);
push(Q, P);
visited[P.x][P.y] = 1;
TG[index][P.x][P.y] = 0;

while (!empty(Q)) {
Point P1;
P1 = top(Q);
pop(Q);

for (int k = 0; k < 4; k++) {
int x = P1.x + dR[k];
int y = P1.y + dC[k];

if (x >= 1 && x <= n && y >= 1 && y <= n && visited[x][y] == 0 && arr[x][y] != 0) {
visited[x][y] = 1;
TG[index][x][y] = TG[index][P1.x][P1.y] + 1;

Point P2;
P2.x = x;
P2.y = y;
push(Q, P2);
}
}
}
}

void reset1() {
for (int v = 1; v <= g; v++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
TG[v][i][j] = -1;
}
}
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
arr[i][j] = 0;
}
}
}

void reset2() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
visited[i][j] = 0;
}
}
}

void reset3() {
for (int i = 1; i <= g; i++) {
visitedV[i] = 0;
}
}

void in() {

input >> n >> g;

reset1();

int gx, gy;
for (int i = 1; i <= g; i++) {
input >> gx >> gy;
G[i].x = gx;
G[i].y = gy;
arr[gx][gy] = 1;
}

int m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
input >> m;
arr[i][j] += m;
}
}
}

void sort() {
for (int i = 1; i < g; i++) {
int sumI = G[i].x + G[i].y;
for (int j = i + 1; j <= g; j++) {
int sumJ = G[j].x + G[j].y;

if (sumI > sumJ) {
swap(G[i].x, G[j].x);
swap(G[i].y, G[j].y);
}

}
}
}

int main() {

output.open("output.txt");

int t;
input >> t;
for (int tc = 1; tc <= t; tc++) {

in();

//sort();

/*for (int v = 1; v <= g; v++) {
cout << G[v].x << " " << G[v].y << endl;
}*/

for (int i = 1; i <= g; i++) {
int x = G[i].x;
int y = G[i].y;

Point P;
P.x = x;
P.y = y;

reset2();

BFS(i, P);
}

int MinTG = MIN;
int MaxV = -1;
reset3();

for (int v1 = 1; v1 <= g; v1++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {

if (TG[v1][i][j] >= 1 && arr[i][j] != 2) {
int countV = 0;
int MaxTG = -1;
int arrIndex[10];
int index = 1;

for (int v2 = 1; v2 <= g; v2++) {
if (TG[v2][i][j] != -1) {
countV++;
arrIndex[index++] = v2;
MaxTG = max(MaxTG, TG[v2][i][j]);
}
}

if (MaxV < countV) {
reset3();
for (int k = 1; k < index; k++)
visitedV[arrIndex[k]] = 1;
MaxV = countV;
MinTG = MaxTG;
}

if (MaxV == countV) {
if (MinTG > MaxTG) {
reset3();
for (int k = 1; k < index; k++)
visitedV[arrIndex[k]] = 1;
MinTG = MaxTG;
}
}
}

}
}
}

//cout << "MinTG: " << MinTG << endl;

output << "Case #" << tc << endl;

if (MinTG == MIN) {
output << "-1" << endl;
}
else {
output << MinTG << endl;
for (int v = 1; v <= g; v++) {
if (visitedV[v] == 0)
output << G[v].x << " " << G[v].y << endl;
}
}

/*cout << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << arr[i][j] << " ";
}
cout << endl;
}
cout << endl;

for (int v = 1; v <= g; v++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << TG[v][i][j] << " ";
}
cout << endl;
}
cout << endl;
}*/
}
}

/*#include <iostream>
#define MIN 999999999
using namespace std;

int n, g;
int r, c;
int arr[21][21];
int visited1[21][21];
int len1[21][21];
int dR[4] = { -1, 0, 1, 0 };
int dC[4] = { 0, 1, 0, -1 };
int visitedV[11];

typedef struct Point {
int x, y;
};

Point V[21];

typedef struct Queue {
int front, rear;
Point data[10001];
};

void init(Queue& Q) {
Q.front = Q.rear = -1;
}

void push(Queue& Q, Point value) {
Q.rear++;
Q.data[Q.rear] = value;
}

Point top(Queue& Q) {
Point temp;
Q.front++;
temp = Q.data[Q.front];
Q.front--;
return temp;
}

void pop(Queue& Q) {
Q.front++;
}

bool empty(Queue& Q) {
if (Q.front == Q.rear)
return true;
return false;
}

Queue Q1;

void BFS(Point S) {
init(Q1);
push(Q1, S);
visited1[S.x][S.y] = 1;
len1[S.x][S.y] = 0;

while (!empty(Q1)) {
Point P;
P = top(Q1);
pop(Q1);

for (int k = 0; k < 4; k++) {
int x = P.x + dR[k];
int y = P.y + dC[k];

if (x >= 1 && x <= n && y >= 1 && y <= n && visited1[x][y] == 0 && arr[x][y] != 0) {
visited1[x][y] = 1;
len1[x][y] = len1[P.x][P.y] + 1;

Point P1;
P1.x = x;
P1.y = y;
push(Q1, P1);
}

}

}

}

void resetKT() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
visited1[i][j] = 0;
len1[i][j] = 0;
arr[i][j] = 0;
}
}
}

void reset() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
visited1[i][j] = 0;
len1[i][j] = 0;
}
}
}

void resetIndex() {
for (int i = 1; i <= g; i++) {
visitedV[i] = 0;
}
}

void input() {

cin >> n >> g;
resetKT();

for (int i = 1; i <= g; i++) {
cin >> r >> c;
V[i].x = r;
V[i].y = c;
arr[r][c] = 1;
}

int m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> m;
arr[i][j] += m;
}
}
}

int main() {
//freopen("vao.txt", "r", stdin);
int t;
cin >> t;
for (int tc = 1; tc <= t; tc++) {

input();

int MinTG = MIN;
int MaxV = -1;

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (arr[i][j] == 1) {

reset();
Point P;
P.x = i;
P.y = j;

BFS(P);

cout << endl;
for (int l = 1; l <= n; l++) {
for (int r = 1; r <= n; r++) {
cout << len1[l][r] << " ";
}
cout << endl;
}
cout << endl;

int countV = 0;
int MaxTG = -1;
int arrV[10];
int index = 1;

for (int z = 1; z <= g; z++) {
int xG = V[z].x;
int yG = V[z].y;
if (visited1[xG][yG] == 1) {
arrV[index++] = z;
countV++;
MaxTG = max(MaxTG, len1[xG][yG]);

}
}

if (MaxTG == 1) {
cout << i << " " << j << endl;
i = n + 1;
j = n+1;
}

if (countV > MaxV) {
resetIndex();

for (int k = 1; k < index; k++)
visitedV[arrV[k]] = 1;

MaxV = countV;
MinTG = MaxTG;
}

else if (countV == MaxV) {
if (MinTG > MaxTG) {
resetIndex();

for (int k = 1; k < index; k++)
visitedV[arrV[k]] = 1;

MaxV = countV;
MinTG = MaxTG;
}
}

}
}
}
cout << "Case #" << tc << endl;

if (MinTG == MIN) {
cout << "-1" << endl;
}
else {
if (MinTG == -1) {
cout << "-1" << endl;
}
else {
cout << MinTG << endl;

if (MaxV != g) {
for (int i = 1; i <= g; i++) {
if (visitedV[i] == 0)
cout << V[i].x << " " << V[i].y << endl;
}
}
}
}
}
return 0;
}*/```