Untitled

 avatar
unknown
plain_text
2 years ago
2.4 kB
4
Indexable
#include<queue>
#define SET -99
using namespace std;
int N_;
struct block {
	int id;
	int row;
	int col;
	int len;
	int dir;
};
int arr[201][201];
int visited[201][201];
block arrID[1000000];
int section = 1;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int cntBlock = -1;
int vs = 1;

void add_set(int r, int c) {
	arr[r][c] = SET;
}

void delete_set(int r, int c) {
	arr[r][c] = 0;
}

void init(int N)
{
	N_ = N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			arr[i][j] = 0;
			visited[i][j] = 0;
		}
	}
	arr[1][1] = SET;
}

queue<pair<int, int>> Q;
void bfs(int r, int c) {
	int row = r, col = c;
	while (!Q.empty())
	{
		row = Q.front().first;
		col = Q.front().second;
		visited[row][col] = vs;
		Q.pop();
		for (int i = 0; i < 4; i++)
		{
			int x = row + dx[i];
			int y = col + dy[i];
			if (x <= 0 || x > N_ || y <= 0 || y > N_) {
				continue;
			}
			else {
				if ((arr[x][y] == 0 || arr[x][y] == SET) && visited[x][y] < vs) {
					visited[x][y] = vs;
					Q.push(make_pair(x, y));

					if (arr[x][y] == SET) {
						delete_set(x, y);
						section--;
					}
				}
			}
		}
	}
	add_set(r, c);
	section++;

}

int addBar(int mID, int mLength, int mRow, int mCol, int mDir)
{
	arrID[mID].id = mID;
	arrID[mID].len = mLength;
	arrID[mID].row = mRow;
	arrID[mID].col = mCol;
	arrID[mID].dir = mDir;

	int tmpX = mRow, tmpY = mCol;
	for (int i = 0; i < mLength; i++)
	{
		arr[tmpX][tmpY] = cntBlock;
		visited[tmpX][tmpY] = 9999;
		tmpX = tmpX + dx[mDir];
		tmpY = tmpY + dy[mDir];
	}
	cntBlock--;

	int x = mRow, y = mCol;
	for (int l = 0; l < mLength; l++)
	{
		for (int i = 0; i < 4; i++)
		{
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx <= 0 || xx > N_ || yy <= 0 || yy > N_) {
				continue;
			}
			if (arr[xx][yy] == 0 && visited[xx][yy] < vs) {
				Q.push(make_pair(xx, yy));
				bfs(xx, yy);
			}
		}
		x = x + dx[mDir];
		y = y + dy[mDir];
	}

	vs++;
	return section;
}



int removeBar(int mID)
{
	int row = arrID[mID].row;
	int col = arrID[mID].col;
	int dir = arrID[mID].dir;
	int len = arrID[mID].len;

	int tmpX = row, tmpY = col;
	for (int i = 0; i < len; i++)
	{
		arr[tmpX][tmpY] += 1;
		if (arr[tmpX][tmpY] < 0)
			visited[tmpX][tmpY] = 9999;
		tmpX = tmpX + dx[dir];
		tmpY = tmpY + dy[dir];
	}

	return section;
}
Editor is loading...