Untitled

 avatar
unknown
plain_text
2 years ago
3.3 kB
11
Indexable
// In Practice, You should use the statndard input/output
#include<iostream>

using namespace std;

int const DOOR = 99999999;
int const HO = 99999990;
int map[16][16],diamond[16][16],n,m,fire[16][16],head,rear,lake,cong,res,dem,visit[16][16];
struct node{
	int r;
	int c;
	node(){};
	node(int _r, int _c){
		r = _r;
		c = _c;
	;}
};
node q[300];
node hugo;
node gate[300];
node h[4] = {node(-1,0),node(0,1),node(1,0),node(0,-1)};

void reset(){
	head = -1;
	rear = -1;
	for (int i =1; i < 16; i++)
	{
		for (int k = 1; k < 16; k++)
		{
			fire[i][k] = -1;
			diamond[i][k] = 0;
			map[i][k] = 0;
			visit[i][k] = -1;
		}
	}
}
void input(){
	cin>>n>>m;
	cin>>hugo.r>>hugo.c;
	int tmp;
	cin>>tmp;
	rear += tmp;
	for (int i = 0; i <= rear; i++)
	{
		cin>>q[i].r>>q[i].c;
		fire[q[i].r][q[i].c] = 0;
	}
	cin>>lake;
	for (int i = 0; i < lake; i++)
	{
		int r,c;
		cin>>r>>c;
		map[r][c] = HO;
		fire[r][c] = HO;
	}
	cin>>cong;
	for (int i = 0; i < cong; i++)
	{
		cin>>gate[i].r>>gate[i].c;
	}

	for (int i = 1; i <= n; i++)
	{
		for (int k = 1; k <= m; k++)
		{
			cin>>diamond[i][k];
		}
	}
}
void bfsFire(){
	
	while (rear > head)
	{
		head++;
		node t = q[head];
		for (int i = 0; i < 4; i++)
		{
			node t1 = t;
			t1.r = t1.r + h[i].r;
			t1.c = t1.c + h[i].c;
			if (t1.r < 1 || t1.r > n || t1.c < 1 || t1.c > m)
			{
				continue;
			}
			if (map[t1.r][t1.c] == HO)
			{
				continue;
			}
			if (fire[t1.r][t1.c] == -1)
			{
				rear++;
				q[rear] = t1;
				fire[t1.r][t1.c] = fire[t.r][t.c] + 1;
			}
		}
	}
}

bool isGate(int hang,int cot){
	for (int i = 0; i < cong; i++)
	{
		if (hang == gate[i].r && cot == gate[i].c) 
			return true;
	}
	return false;
}
void dfs(int r, int c){
	if (isGate(r,c))
	{
		if (dem > res) res = dem;
		return;
	}
	if (visit[r][c] >= fire[r][c])
	{
		return;
	}
	
	for (int i = 0; i < 4; i++)
	{
		node t = node(r,c);
		t.r = t.r + h[i].r;
		t.c = t.c + h[i].c;
		if (t.r < 1 || t.r > n || t.c < 1 || t.c > m)continue;

		if (map[r][c] == 0 && visit[t.r][t.c] == -1)
		{
			if (visit[r][c] + 1 < fire[t.r][t.c])
			{
				visit[t.r][t.c] = visit[r][c] + 1;
				dem += diamond[t.r][t.c];
				dfs(t.r,t.c);
				dem -= diamond[t.r][t.c];
				visit[t.r][t.c] = visit[r][c] - 1;
			}
		}
		if (map[r][c] == HO && visit[t.r][t.c] == -1)
		{
			if (visit[r][c] + 2 < fire[t.r][t.c])
			{
				visit[t.r][t.c] = visit[r][c] + 2;
				dem += diamond[t.r][t.c];
				dfs(t.r,t.c);
				dem -= diamond[t.r][t.c];
				visit[t.r][t.c] = visit[r][c] - 2;
			}
		}
	}
}

bool check(){
	for (int i = 0; i < cong; i++)
		if (visit[gate[i].r][gate[i].c] != -1) return true;

	return false;
}
int main()
{
	int test_case;
	int T;
	
	freopen("Text.txt", "r", stdin);
	cin >> T;

	for(test_case = 1; test_case <= T; ++test_case)
	{
		reset();
		input();
		bfsFire();
		dem = 0;
		res = 0;

		visit[hugo.r][hugo.c] = 0;
		dem+=diamond[hugo.r][hugo.c];

		dfs(hugo.r,hugo.c);

		if (check())
		{
			cout << "#" << test_case << " " << res << endl;
		}
		// Print the answer to standard output(screen).
		
	}
	return 0;//Your program should return 0 on normal termination.
}
Editor is loading...