Untitled

 avatar
unknown
plain_text
a year ago
2.8 kB
4
Indexable
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int t, m, n, sr, sc, fire, water, out, mapkimcuong[15][15];
int map[15][15], mapout[15][15], firemap[15][15], visited1[15][15], visited2[15][15];
int r, c, front, rear, q[1000], Anwer, kimcuong, maxkc, check;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

struct Queue
{
	void initQueue()
	{
		front = rear = -1;
	}

	int isEmpty()
	{
		if (front == rear)
			return 1;
		return 0;
	}

	void enQueue(int x)
	{
		rear++;
		q[rear] = x;
	}

	int deQueue()
	{
		if (!isEmpty())
		{
			front++;
			return q[front];
		}
		return -1;
	}

};

void BFS(int x, int y)
{
	Queue q1, q2;
	q1.enQueue(x);
	q2.enQueue(y);
	visited1[x][y] = 1;
	while (!q1.isEmpty())
	{
		int u = q1.deQueue();
		int v = q2.deQueue();
		for (int k = 0; k < 4; k++)
		{
			int tx = u + dx[k];
			int ty = v + dy[k];
			if (tx > 0 && tx <= n && ty > 0 && ty <= m && !visited1[tx][ty] && map[tx][ty] != 1)
			{
				visited1[tx][ty] = 1;
				q1.enQueue(tx);
				q2.enQueue(ty);
				firemap[tx][ty] = firemap[u][v] + 1;

			}
		}
	}

}

void backtrack(int x, int y, int time)
{
	visited2[x][y] = 1;
	if (map[x][y])
	{
		check = 1;
		if (maxkc < kimcuong)
			maxkc = kimcuong;
	}

	for (int k = 0; k < 4; k++)
	{
		int tx = x + dx[k];
		int ty = y + dy[k];

		if (tx > 0 && tx <= n && ty > 0 && ty <= m && !visited2[tx][ty] && time < firemap[tx][ty])
		{
			visited2[tx][ty] = 1;
			kimcuong += mapkimcuong[tx][ty];
			backtrack(tx, ty, time + 1);
			visited2[tx][ty] = 0;
			kimcuong -= mapkimcuong[tx][ty];
		}
	}


}


int main()
{
	freopen("input.txt", "r", stdin);
		cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{
		cin >> n >> m >> sr >> sc;

		cin >> fire; //goi lua
		for (int i = 0; i < fire; i++)
		{
			cin >> r >> c;
			firemap[r][c] = 1;
		}

		cin >> water; //goi nuoc
		for (int i = 0; i < water; i++)
		{
			cin >> r >> c;
			map[r][c] = 1;
		}

		cin >> out;
		for (int i = 0; i < out; i++)
		{
			cin >> r >> c;
			mapout[r][c] = 1;
		}

		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				cin >> mapkimcuong[i][j];
				visited1[i][j] = visited2[i][j] = 0;
			}
		}

		map[sr][sc] = 2;

		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				if (firemap[i][j] == 1)
				{
					BFS(i, j);
				}
			}
		}
		

		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j  <= m; j ++)
			{
				cout << firemap[i][j] << " ";
			}
			cout << endl;
		}

		check = 0;
		maxkc = 0;
		backtrack(sr, sc, 0);

		if (check)
		{
			cout << tc << " " << maxkc << endl;
		}
		else
			cout << tc << " " << -1 << endl;
	}

	return 0;
}
Editor is loading...
Leave a Comment