Untitled
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...