Untitled
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