POJ 1429 BFS+優先隊列

題目：http://poj.org/problem?id=3984

很經典用BFS解決的了。

#include<iostream>  
#include<string.h>  
#include<queue>  
#define INF 1e18
#define inf 1e9
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std ;
typedef long long ll;
typedef unsigned long long ull;
const int n = ;
int dx[]={,-,,};
int dy[]={,,-,};
bool mp[][];
struct node{
    int x,y,step,nx,ny;
    bool operator < (const node &n1)const{
        return step > n1.step;
    }
    void count(){
        this->step = (n-x)+(n-y);
    }
};
struct node1{
    int nx,ny;
    void init(node n){
        this->nx = n.nx;
        this->ny = n.ny;
    }
};
priority_queue<node> q;
node1 m[][];
bool outside(node n1){
    if(mp[n1.x][n1.y]) return false;
    if(n1.x > n || n1.x < ) return false;
    if(n1.y > n || n1.y < ) return false;
    return true;
}
void bfs(){
    while(!q.empty()) q.pop();
    node now,next;
    now.x = ,now.y = ;
    now.count();
    q.push(now);
    while(!q.empty()){
        now = q.top();
        q.pop();
//      cout<<now.x<<' '<<now.y<<endl;
        for(int i =  ; i <  ; i++){
            next.x = now.x+dx[i];
            next.y = now.y+dy[i];
            next.nx = now.x,next.ny = now.y;
            if(!outside(next)) continue;
            m[next.x][next.y].init(next);
            mp[next.x][next.y] = true;
            next.count();
            q.push(next);
            if(next.x == n&&next.y ==n) return;
        }
    }   
}
void print(int x,int y){
    if(x != ||y != )
        print(m[x][y].nx,m[x][y].ny);
    cout<<"("<<x-<<", "<<y-<<")"<<endl;
}
int main(){
    memset(m,,sizeof(m));
    for(int i =  ; i <= n ; i++)
        for(int j =  ; j <= n ; j++)   
        cin>>mp[i][j];
    bfs();  
    print(,);
    return ;
}