Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.9 kB
3
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

int n, m, sr, sc;
int fire, lake, out;
int firex[100], firey[100];
int lakex[100], lakey[100];
int outx[100], outy[100];
int kimcuong[100][100];
int front = -1;
int rear = -1;
int Qx[10000000], Qy[10000000];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int vs_fire[100][100];
int vs_out[100][100];
int ans;
int vs_hugo[100][100];

void doc()
{
	cin >> n >> m >> sr >> sc;
	//reset bien
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			vs_fire[i][j] = -1;
			vs_out[i][j] = 0;
			kimcuong[i][j] = 0;
			vs_hugo[i][j] = -1;
		}
	ans = 0;
	vs_hugo[sr][sc] = 0;
	//doc dam chay
	cin >> fire;
	for (int i = 1; i <= fire; i++)
	{
		cin >> firex[i] >> firey[i];
		vs_fire[firex[i]][firey[i]] = 0;
	}
	//doc ho
	cin >> lake;
	for (int i = 1; i <= lake; i++)
	{
		cin >> lakex[i] >> lakey[i];
		vs_fire[lakex[i]][lakey[i]] = -2;
	}
	//doc loi ra
	cin >> out;
	for (int i = 1; i <= out; i++)
	{
		cin >> outx[i] >> outy[i];
		vs_out[outx[i]][outy[i]] = 1;
	}
	//doc mang kim cuong
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) cin >> kimcuong[i][j];

	

}

bool checkbien(int x, int y)
{
	if (x<1 || x>n || y <1 || y>m) return false;
	return true;
}

void push(int x, int y)
{
	rear++;
	Qx[rear] = x;
	Qy[rear] = y;
}

void pop(int& x, int& y)
{
	front++;
	x = Qx[front];
	y = Qy[front];
}

void Bfs_fire()
{
	front = rear = -1;
	for (int i = 1; i <= fire; i++) 	push(firex[i], firey[i]);

	
	int x, y;
	while (front != rear)
	{ 
		pop(x, y);
		for (int i = 0; i < 4; i++)
		{
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (checkbien(xx, yy))
			{
				if (vs_fire[xx][yy] == -1)
				{
					push(xx, yy);
					vs_fire[xx][yy] = vs_fire[x][y] + 1;
				}
			}
		}
	}
}

void Backtrack_hugo(int x, int y, int sum)
{

	if (vs_hugo[x][y] >= vs_fire[x][y] && vs_fire[x][y] > -1) return;

	if (ans < sum)
	{
		if (vs_out[x][y] == 1) ans = sum;
	}

	for (int i = 0; i < 4; i++)
	{
	
		if (checkbien(x+dx[i], y+dy[i]) && vs_hugo[x + dx[i]][y + dy[i]] == -1)
		{
			if(vs_fire[x][y] == -2)
			{
				vs_hugo[x + dx[i]][y + dy[i]] = vs_hugo[x][y] + 2;
				Backtrack_hugo(x + dx[i], y + dy[i], sum + kimcuong[x + dx[i]][y + dy[i]]);
				vs_hugo[x + dx[i]][y + dy[i]] = -1;
			}
			else
			{
				vs_hugo[x + dx[i]][y + dy[i]] = vs_hugo[x][y] + 1;
				Backtrack_hugo(x + dx[i], y + dy[i], sum + kimcuong[x + dx[i]][y + dy[i]]);
				vs_hugo[x + dx[i]][y + dy[i]] = -1;
			}
		}
		
	}

}


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

		Backtrack_hugo(sr, sc, kimcuong[sr][sc]);
		
		if (ans == 0) ans = -1;
		cout << "Case #" << tc << endl;
		cout << ans << endl;



	}	
}