Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.2 kB
2
Indexable
Never
#include <iostream>
#define MAX_N 30
using namespace std;

int qx[1000], qy[1000],tx, ty, tmpx, tmpy, front, rear;

int n, map[31][31];
void initQueue() {
	front = rear = -1;
}

int isEmpty() {
	return front == rear;
}

void enQueue(int x, int y) {
	qx[++rear] = x;
	qy[rear] = y;
}

void deQueue(int &tmpx, int &tmpy) {
	tmpx = qx[++front];
	tmpy = qy[front];
}

int isValid() {
	return tx >= 0 && tx < n && ty >= 0 && ty < n && !map[tx][ty];
}

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

//Check character
void resetVisited() {
	for(int r=0; r<n; r++) {
		for(int c=0; c<n; c++) {
			visited[r][c] = 0;
		}
	}
}
bool visited[31][31];
bool is_valid(int x, int y) {
	return x >=0 && y < n && y >=0 && y < n && map[x][y] == 0 && !visited[x][y];
}
bool dfs(int x, int y, int xen, int yen){
	if(x == xen && y == yen) {
		return true;
	}
	visited[x][y] = true;
	for(int i = 0; i<4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(is_valid(nx, ny)) {
			if(dfs(nx, ny, xen, yen)) {
				return true;
			}
		}
	}
	return false;
}

void init(int N, int mMap[MAX_N][MAX_N])
{
	initQueue();
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			map[i][j] = mMap[i][j];
		}
	}

	return;
}

int push(int mRockR, int mRockC, int mDir, int mGoalR, int mGoalC)
{
	int res = 9999999;
	int times = 0;
	enQueue(mRockR, mRockC);
	while(!isEmpty()) {
		deQueue(tmpx, tmpy);
		if(tmpx == mGoalR && tmpy == mGoalC) {
			res = times < res ? times : res;
		}
	}
	for(int k=0; k<4; k++) {
		resetVisited();
		bool checkDir = false;
		if(mDir == (k+2)%4) {
			checkDir = true;
		} else {
			if(mDir == 0 && dfs(mRockR - 1, mRockC, mRockR + 1, mRockC) == true) checkDir = true;
			else if(mDir == 1 && dfs(mRockR , mRockC + 1, mRockR, mRockC - 1) == true) checkDir = true;
			else if(mDir == 2 && dfs(mRockR + 1, mRockC, mRockR - 1, mRockC) == true) checkDir = true;
			else if(mDir == 3 && dfs(mRockR , mRockC - 1, mRockR, mRockC + 1) == true) checkDir = true;
		}
		if(checkDir == true) {
			tx = tmpx + dx[k];
			ty = tmpy + dy[k];
			if(isValid()) {
				enQueue(tx, ty);
			}
		}
	}
	return 0;
}
Leave a Comment