Gold mining

Gold mining 1
Given a map of gold mine which can be represented as a NxN matrix
In this map, there are several gold mines that locates on random places (maximum 4 mines each map). A camp will be setup in the map for mining the gold. Every day, workers will go from the camp to gold mines location. In order to reduce the cost, company want to setup the camp so that the distance from it to mining location is optimized.
Let consider below 5x5 map :
 
 - Worker can not go through the rock
 - It takes 1 hour to travel a cell in map
There are two mines, from start point (camp location), it would take 4h to go to each gold mine. Let's suppose the final cost will be the highest cost among them, then if we put the camp as above figure, the final cost will be 4.
Now, we consider other example :
 
In the 3rd example, the final cost will be minimum (1)
[Input]
The first line of input will be the number of test case T (T ≤ 50)
In each TC :
 - The first line will give the size of map N (N ≤ 20) and the number of gold mines G (2 ≤ G ≤ 4)
 - The next G lines will give location R (row) & C (column) of gold mine (1-base indexed)
- The next N lines will give the map's data : 1 represents the road & gold mines, 0 represents the rock (can not go through)

[Output]
Your program should output the Minimum final cost for traveling from camp to gold mines.
Case #1
1
Case #2
2
Case #3
2
Case #4
7
Case #5
6

[Constraints]
- You can move on 4 directions (up/left/down/right)
- You can not setup the camp on gold mine location or rock
- You can go pass a gold mine then go to other gold mine
- You must place camp so that workers can go to all gold mines



Gold mining 2
Given a map of gold mine which can be represented as a NxN matrix
In this map, there are several gold mines that locates on random places (maximum 4 mines each map). A camp will be setup in the map for mining the gold. Every day, workers will go from the camp to gold mines location. In order to reduce the cost, company want to setup the camp so that the distance from it to mining location is optimized.
Let consider below 5x5 map :
 
 - Worker can not go through the rock
 - It takes 1 hour to travel a cell in map
There are two mines, from start point (camp location), it would take 4h to go to each gold mine. Let's suppose the final cost will be the highest cost among them, then if we put the camp as above figure, the final cost will be 4.
Now, we consider other example :
 
In the 3rd example, the final cost will be minimum (1)
[Input]
The first line of input will be the number of test case T (T ≤ 50)
In each TC :
 - The first line will give the size of map N (N ≤ 20) and the number of gold mines G (2 ≤ G ≤ 4)
 - The next G lines will give location R (row) & C (column) of gold mine (1-base indexed)
- The next N lines will give the map's data : 1 represents the road & gold mines, 0 represents the rock (can not go through)

[Output]
On the first line : you should output the Minimum final cost for traveling from camp to gold mines. If there is no way to reach all gold mines, print   -1 as answer
Case #1
1
Case #2
2
Case #3
2
Case #4
7
Case #5
6

[Constraints]
- You can move on 4 directions (up/left/down/right)
- You can not setup the camp on gold mine location or rock
- You can go pass a gold mine then go to other gold mine
- You should place camp in order to Maximize the number of reachable gold mines


Gold mining 3
Given a map of gold mine which can be represented as a NxN matrix
In this map, there are several gold mines that locates on random places (maximum 4 treasure each map). A camp will be setup in the map for mining the gold. Every day, workers will go from the camp to gold mines location. In order to reduce the cost, company want to setup the camp so that the distance from it to mining location is optimized.
Let consider below 5x5 map :
 
 - Worker can not go through the rock
 - It takes 1 hour to travel a cell in map
There are two mines, from start point (camp location), it would take 4h to go to each gold mine. Let's suppose the final cost will be the highest cost among them, then if we put the camp as above figure, the final cost will be 4.
Now, we consider other example :
 
In the 3rd example, the final cost will be minimum (1)
[Input]
The first line of input will be the number of test case T (T ≤ 50)
In each TC :
 - The first line will give the size of map N (N ≤ 20) and the number of gold mines G (2 ≤ G ≤ 4)
 - The next G lines will give location R (row) & C (column) of gold mine (1-base indexed)
- The next N lines will give the map's data : 1 represents the road & gold mines, 0 represents the rock (can not go through)

[Output]
On the first line : you should output the Minimum final cost for traveling from camp to gold mines. If there is no way to reach all gold mines, print   -1 as answer
If there is any gold mines that can not be reach, you should print out their locations, each mine in one line from second line (with same order of them in the input)

[Constraints]
- You can move on 4 directions (up/left/down/right)
- You can not setup the camp on gold mine location or rock
- You can go pass a gold mine then go to other gold mine
- You should place camp in order to Maximize the number of reachable gold mines



#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int qx[1000], qy[1000], f = -1, r = -1;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void Push(int x, int y) {
	r++;
	qx[r] = x;
	qy[r] = y;
}

void Pop(int& x, int& y) {
	f++;
	x = qx[f];
	y = qy[f];
}
void Reset() {
	f = r = -1;
}
bool isEmpty() {
	return f == r;
}

int n, m, g;
int map[50][50];
int visit[50][50];
int gm[101][3];
int kq[101][3];
int minPath,maxGm,curGm,curPath;
void saveKq() {
	for (int i = 1; i <= g; i++) {
		kq[i][0] = gm[i][0];
		kq[i][1] = gm[i][1];
		kq[i][2] = gm[i][2];
	}
}

void setVisitGm(int x, int y) {
	for (int i = 1; i <= g; i++) {
		if (x == gm[i][0] && y == gm[i][1]) {
			gm[i][2] = 1;
			break;
		}
	}
}
void resetVisit() {
	for (int i = 1; i <= g; i++) gm[i][2] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visit[i][j] = -1;
		}
	}
}

void bfs(int r, int c) {
	Reset();
	Push(r, c);
	visit[r][c] = 0;
	curGm = 0;
	curPath = 0;
	while (!isEmpty()) {
		int x, y;
		Pop(x, y);
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && visit[xx][yy] == -1 && map[xx][yy]!=0) {
				Push(xx, yy);
				visit[xx][yy] = visit[x][y] + 1;
				if (map[xx][yy] == 2) {
					curGm++;
					setVisitGm(xx, yy);
					curPath = max(curPath, visit[xx][yy]);
				}
			}
		}
	}
}
int main() {
	freopen("Text.txt", "r", stdin);
	int T;
	cin >> T;

	for (int t = 1; t <= T; t++) {
		cin >> n >> g;
		for (int i = 1; i <= g; i++) {
			cin >> gm[i][0] >> gm[i][1];
			gm[i][2] = 0;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> map[i][j];
			}
		}
		for (int i = 1; i <= g; i++) {
			map[gm[i][0]][gm[i][1]] = 2;
		}
		maxGm = 0;
		minPath = 1e9;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (map[i][j] == 1) {
					resetVisit();
					bfs(i, j);
					if (curGm > maxGm) {
						maxGm = curGm;
						minPath = curPath;
						saveKq();
					}
					else if (curGm == maxGm && curPath != 0) {
						if (curPath < minPath) {
							minPath = curPath;
							saveKq();
						}
					}
				}
			}
		}
		cout << "Case #" << t << endl;
		if (minPath == 1e9) {
			cout << -1 << endl;
		}
		else {
			cout << minPath << endl;
			for (int i = 1; i <= g; i++) {
				if (kq[i][2] == 0) {
					cout << kq[i][0] << " " << kq[i][1] << endl;
				}
			}
		}
	}

	return 0;
}