Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一直RE, 求解释啊,我是用的BFS, 测试数据都能过啊

Posted by tavares at 2014-01-28 15:58:20 on Problem 3009
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator