Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
一直RE, 求解释啊,我是用的BFS, 测试数据都能过啊#include <iostream> #include <vector> #include <queue> using namespace std; int startx, starty; int goalx, goaly; int** initBoard; int moves; bool havePath; class node{ public: int moveCount; int x, y; int** board; node() {board = new int*[22]; for(int i = 0; i < 22; i++)board[i] = new int[22];} }; queue<node* > qu; int width, height; void copyBoard(int** board, int** tocopy, int h, int w) { for(int i = 0; i < h; i++) for(int j = 0; j < w; j++){ board[i][j] = tocopy[i][j]; } } int main() { int type; initBoard = new int*[22]; for(int i = 0; i < 22; i++) initBoard[i] = new int[22]; cin >> width >> height; while(width || height) { // init graph for(int i = 0; i < height; i++) for(int j = 0; j < width; j++){ cin >> initBoard[i][j]; if(initBoard[i][j] == 2){ startx = i; starty = j; } else if(initBoard[i][j] == 3){ goalx = i; goaly = j; } } //cout << "init "<< initBoard[0][3] << endl; node* n = new node(); n->moveCount = 0; n->x = startx; n->y = starty; // cur pos; copyBoard(n->board, initBoard, height, width); //cout << "copy:" << n->board[0][3] << endl; havePath = false; qu.push(n); while(!qu.empty()) { // consider four directions node* nd = qu.front(); int mc = nd->moveCount + 1; if(mc > 10) break; qu.pop(); int xpos = nd->x; int ypos = nd->y; // four directions if(xpos - 1 >= 0 && nd->board[xpos - 1][ypos] != 1){ for(int i = xpos - 1; i >= 0; i--){ if(nd->board[i][ypos] == 3){ // 剪枝 havePath = true; moves = mc; break; } else if(nd->board[i][ypos] == 1){ // hit a block node* newNode = new node(); newNode->moveCount = mc; newNode->x = i + 1; newNode->y = ypos; copyBoard(newNode->board, nd->board, height, width); newNode->board[i][ypos] = 0; // the block is hit qu.push(newNode); //cout << "push " << newNode->x << " " << newNode->y << endl; break; } } } if(havePath) break; if(xpos + 1 < height && nd->board[xpos + 1][ypos] != 1){ for(int i = xpos + 1; i < height; i++){ if(nd->board[i][ypos] == 3){ // 剪枝 havePath = true; moves = mc; break; } else if(nd->board[i][ypos] == 1){ // hit a block node* newNode = new node(); newNode->moveCount = mc; newNode->x = i - 1; newNode->y = ypos; copyBoard(newNode->board, nd->board, height, width); newNode->board[i][ypos] = 0; // the block is hit qu.push(newNode); //cout << "push " << newNode->x << " " << newNode->y << endl; break; } } } if(havePath) break; //cout << bd[0][3] << endl; if(ypos - 1 >= 0 && nd->board[xpos][ypos - 1] != 1){ for(int i = ypos - 1; i >= 0; i--){ if(nd->board[xpos][i] == 3){ // 剪枝 havePath = true; moves = mc; break; } else if(nd->board[xpos][i] == 1){ // hit a block node* newNode = new node(); newNode->moveCount = mc; newNode->x = xpos; newNode->y = i + 1; copyBoard(newNode->board, nd->board, height, width); newNode->board[xpos][i] = 0; // the block is hit qu.push(newNode); //cout << "push " << newNode->x << " " << newNode->y << endl; break; } } } if(havePath) break; //cout << bd[0][3] << endl; if(ypos + 1 < width && nd->board[xpos][ypos + 1] != 1){ for(int i = ypos + 1; i < width; i++){ if(nd->board[xpos][i] == 3){ // 剪枝 havePath = true; moves = mc; break; } else if(nd->board[xpos][i] == 1){ // hit a block node* newNode = new node(); newNode->moveCount = mc; newNode->x = xpos; newNode->y = i - 1; copyBoard(newNode->board, nd->board, height, width); newNode->board[xpos][i] = 0; // the block is hit qu.push(newNode); //cout << "push " << newNode->x << " " << newNode->y << endl; break; } } } if(havePath) break; } if(havePath && moves <= 10){ cout << moves <<endl; } else{ cout << -1 << endl; } for(int i = 0; i < height; i++){ delete []initBoard[i]; } delete []initBoard; cin >> width >> height; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator