Untitled

HUGO

Input

Dòng đầu là số lượng test case T (T <= 50).

Dòng đầu của mỗi test case là 4 số N, M, SR, SC tương ứng là số hàng, số cột của khu rừng và tọa độ hàng, cột mà Hugo đang đứng. ( 4 <= N, M <= 15).

3 dòng tiếp theo, bắt đầu của mỗi dòng tương ứng là số lượng K các đám cháy hiện có, các hồ và các lối thoát, 2K số tiếp theo trên dòng là tọa độ tương ứng. N dòng tiếp theo sẽ là bản đồ mô tả số lượng kim cương D tại mỗi khu vực trong khu rừng. (0 <= D <= 1000)

Output

In mỗi test case trên 2 dòng, dòng đầu tiên là "Case #x", với x là số thứ tự của test case.

Dòng tiếp theo là số lượng kim cương lớn nhất mà Hugo có thể thu được, nếu Hugo không thể thoát ra khỏi khu rừng, in ra -1.

Sample

Input

5 <- Số lượng test case

4 4 1 2 <- Test case 1, khu rừng có kích thước 4x4, Hugo đang ở ô (1, 2)

2 1 1 4 1 <- 2 Khu vực bắt đầu cháy ở (1, 1) và (4, 1)

4 1 3 2 1 3 3 3 4 <- 4 Khu vực là hồ ở (1, 3), (2, 1), (3, 3) và (3, 4)

2 2 4 3 4 <- 2 lối thoát ở ô (2, 4) và (3, 4)

0 0 10 20 <- Số lượng kim cương hàng 1

9 3 2 5 <- Số lượng kim cương hàng 2

0 0 0 0 <- Số lượng kim cương hàng 3

0 10 0 100 <- Số lượng kim cương hàng 4

...

Output

Case #1

10  <- Số lượng kim cương lớn nhất mà Hugo có thể thu được

Case #2

45

Case #3

250

Case #4

643

Case #5

328


// code
#include <iostream>
using namespace std;
int T,N,M,SR,SC;
int map[20][20];
int fireX[400], fireY[400], lakeX[400], lakeY[400], exitX[400], exitY[400];
int diamond[20][20];
int visited[20][20];
int fireMap[20][20];
int x,y,u,v;
int startX, startY;
int numFire;
int numLake;
int numExit;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
// Queue
int QueueX[400], QueueY[400];
int rearX, rearY, frontX, frontY;

//Queue X
void initQueueX()
{
	rearX = frontX = -1;
}

int isEmptyX() 
{
	if (rearX == frontX)
	{
		return 1;
	}
	return 0;
}

void enQueueX(int value)
{
	rearX++;
	QueueX[rearX] = value;
}

int deQueueX()
{
	if (!isEmptyX())
	{
		frontX++;
		return QueueX[frontX];
	}
	return -1;
}

// Queue Y

void initQueueY()
{
	rearY = frontY = -1;
}

int isEmptyY() 
{
	if (rearY == frontY)
	{
		return 1;
	}
	return 0;
}

void enQueueY(int value)
{
	rearY++;
	QueueY[rearY] = value;
}

int deQueueY()
{
	if (!isEmptyY())
	{
		frontY++;
		return QueueY[frontY];
	}
	return -1;
}


void DFS()
{

}


// BFS lua
void BFS(int stX, int stY)
{
	initQueueX();
	initQueueY();
	enQueueX(stX);
	enQueueY(stY);
	visited[stX][stY] = 0;
	while (!isEmptyX())
	{
		x = deQueueX();
		y = deQueueY();
		for (int k = 0; k < 4; k++)
		{
			u = x + dx[k];
			v = y + dy[k];
			
			if (u >= 0 && u < N && v >= 0 && v < M && visited[u][v] == -1 && map[u][v] != 2)
			{
				visited[u][v] = visited[x][y] + 1;
				enQueueX(u);
				enQueueY(v);
			}
		}
	}
}

//cho chay het map
// lay min cac matran lua chay
// Hugo - DFS(int x, int y, )
void readInput()
{
	cin >> N >> M >> startX >> startY;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			map[i][j] = 0;
			visited[i][j] = -1;
		}
	}
	cin >> numFire;
	for (int i = 0; i < numFire; i++)
	{
		
		cin >> fireX[i] >> fireY[i];
		map[fireX[i]][fireY[i]] = 1;
	}
	cin >> numLake;
	for (int i = 0; i < numLake; i++)
	{
		cin >> lakeX[i] >> lakeY[i];
		map[lakeX[i]][lakeY[i]] = 2;
	}

	cin >> numExit;
	for (int i = 0; i < numExit; i++)
	{
		cin >> exitX[i] >> exitY[i];
		map[exitX[i]][exitY[i]] = 3;
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> diamond[i][j]; 
		}
	}
}

int main()
{
	cin >> T;
	for (int tc = 1; tc <= T; tc++)
	{
		//nhap map
		readInput();

	}

	return 0;
}