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