Untitled

 avatar
unknown
plain_text
a year ago
2.4 kB
3
Indexable
#include<iostream>

using namespace std;

int n, m, sr, sc;
int fire, lake, exi;
int F[600], L[600], E[600];
int M[20][20], A[20][20];
int S[2][100000];
int top, bot;
int visited[20][20];
int FL[20][20];
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
int kq, maxx;
bool checkexit;

void back2(int tgian, int x, int y, int kq)
{
	if (A[x][y] == 2)
	{
		if (kq > maxx) maxx = kq;
		checkexit = true;
	}
	for (int i = 0; i < 4; i++)
	{
		int xnew = x + dx[i], ynew = y + dy[i];
		if (xnew >= 1 && xnew <= n && ynew >= 1 && ynew <= m)
		{
			if ((tgian + 1 < FL[xnew][ynew] || FL[xnew][ynew]<0 )&& visited[xnew][ynew] == 0)
			{
				visited[xnew][ynew] = 1;
				if (FL[xnew][ynew] == 9998)
				{
					back2(tgian + 2, xnew, ynew, kq + M[xnew][ynew]);
					visited[xnew][ynew] = 0;
				}
				else
				{
					back2(tgian + 1, xnew, ynew, kq + M[xnew][ynew]);
					visited[xnew][ynew] = 0;
				}
			}
		}
	}
}

int main()
{
	int t; cin >> t;
	for (int tc = 1; tc <=t; tc++)
	{
		cin >> n >> m >> sr >> sc;
		cin >> fire;
		for (int i = 0; i < 2 * fire; i++) cin >> F[i];
		cin >> lake;
		for (int i = 0; i < 2 * lake; i++) cin >> L[i];
		cin >> exi;
		for (int i = 0; i < 2 * exi; i += 2)
		{
			cin >> E[i] >> E[i + 1];
			A[E[i]][E[i + 1]] = 2;
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				cin >> M[i][j];
				visited[i][j] = 0;
				FL[i][j] = 0;
			}
		}
		for (int i = 0; i < 2 * lake; i += 2)
		{
			FL[L[i]][L[i + 1]] = 9999;
		}
		//
		top = bot = -1;
		//
		for (int i = 0; i < 2 * fire; i += 2)
		{
			//push vao queue
			top++;
			S[0][top] = F[i];
			S[1][top] = F[i + 1];
			FL[F[i]][F[i + 1]] = 1;
		}
		while (top != bot)
		{
			bot++;
			int x = S[0][bot];
			int y = S[1][bot];
			for (int k = 0; k < 4; k++)
			{
				int xnew = x + dx[k];
				int ynew = y + dy[k];
				if (FL[xnew][ynew] == 0 && xnew <= n && xnew >= 1 && ynew <= m && ynew >= 1)
				{
					top++;
					S[0][top] = xnew;
					S[1][top] = ynew;
					FL[xnew][ynew] = FL[x][y] + 1;
				}
			}
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++) FL[i][j] = FL[i][j] - 1;
		}

		visited[sr][sc] = 1;
		kq = M[sr][sc];
		maxx = 0;
		checkexit = false;
		back2(0, sr, sc, kq);
		cout << "Case #" << tc << endl;
		if (checkexit) cout << maxx << endl;
		else cout << -1 << endl;
	}
	return 0;
}
Editor is loading...
Leave a Comment