Untitled

mail@pastecode.io avatar
unknown
plain_text
7 days ago
2.6 kB
3
Indexable
Never
#include<iostream>
using namespace std;

int t, m, n, sr, sc, a[100][100], k, xfire, yfire, xwater, ywater, xout, yout;
int damchay[100][100], visited[100][100], kimcuong[100][100], fire, water , out , maxkc, sokc;

int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};

void lua_lan(int a[100][100], int check)
{
	if(check  == 1)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				if(a[i][j] == 4)
				{
					for (int k = 0; k < 4; k++)
					{
						int tx = i + dx[k];
						int ty = j + dy[k];
						if( a[tx][ty] == 3)
						{
							a[tx][ty] = 3;
						}
						a[tx][ty] = 4;
					}
				}
			}
		}
	}
	else if(check == 0)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				if(a[i][j] == 5)
				{
					a[i][j] = 0;
				}
			}
		}

	} 

}

//void BFS(int x, int y)
//{
//
//
//}

void backtrack(int x, int y)
{
	if(a[x][y] == 4)
	{
		if(maxkc < sokc)
			maxkc = sokc;
		return;
	}

		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 && !visited[tx][ty] && a[tx][ty] != 4 && a[tx][ty] != 5)
			{
				if(a[tx][ty] == 3)
				{
					visited[tx][ty] = 1;
					sokc += kimcuong[tx][ty];
					lua_lan(a, 1);
					lua_lan(a , 1);
					backtrack(tx, ty);
					lua_lan(a, 0);
					visited[tx][ty] = 0;
					sokc += kimcuong[tx][ty];

				}
				else
				{
					visited[tx][ty] = 1;
					sokc += kimcuong[tx][ty];
					lua_lan(a, 1);
					backtrack(tx, ty);
					lua_lan(a, 0);
					visited[tx][ty] = 0;
					sokc += kimcuong[tx][ty];
				}

			}

		}

}

int main()
{
	freopen("t.txt", "r", stdin);
	cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{
		cin >> n >> m >> sr >> sc;
		
			cin >> fire;//vi tri ngon lua
			for (int j = 0; j < fire; j++)
			{
				cin >> xfire >> yfire;
				a[xfire][yfire] = 2;
			}

			cin >> water;
			for (int i = 0; i < water; i++)
			{
				cin >> xwater >> ywater;
				a[xwater][ywater] = 3;
			}

			cin >> out;
			for (int i = 0; i < out; i++)
			{
				cin >> xout >> yout;
				a[xout][yout] = 4;
			}
	

		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				cin >> kimcuong[i][j];
				visited[i][j] = 0;
			}
		}
		a[sr][sc] = 1;
		visited[sr][sc] = 1;
		maxkc = 0;
		backtrack(sr, sc);

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


Leave a Comment