Saturday 21 March 2009

POJ ( acm.pku.edu.cn ) 1915

以前写过求马的周游路线的算法——相对而言这道题就没啥难度了。



#include <algorithm>
#include <iostream>
#include <utility>
#include <deque>
using namespace std;
typedef std::pair<int,int> move;
enum state {OUT=0, OK=1, VISITED=2, TARGET=-1};
typedef state board[304][304];

const int MOVES[8][2]={
{-1,-2}, {-2,-1}, {-1,2}, {-2,1}, {1,-2}, {2,-1}, {1,2}, {2,1}
};

int go(board b,int x,int y){ //BFS
if(b[x][y]==TARGET)
return 0;
deque<int> stepx[2];
deque<int> stepy[2];
stepx[0].push_back(x);
stepy[0].push_back(y);
int level=0;
int l1=0,l2=1;
while(true){
++level;
if(stepx[l1].empty()) return -1;
while(!stepx[l1].empty()){
x=stepx[l1].front();
stepx[l1].pop_front();
y=stepy[l1].front();
stepy[l1].pop_front();
for(int i=0;i<8;++i){
int tx=x+MOVES[i][0],ty=y+MOVES[i][1];
if (b[tx][ty]==OUT) continue;
if (b[tx][ty]==VISITED) continue;
if (b[tx][ty]==TARGET) return level;
b[tx][ty]=VISITED;
stepx[l2].push_back(tx);
stepy[l2].push_back(ty);
}
}
l1^=l2^=l1^=l2;
}
return -1;
}

int main() {
int N;
for(cin>>N;N;--N){
int size; cin>>size;
int xf,yf,xt,yt; cin>>xf>>yf>>xt>>yt;
board b={OUT};
for(int i=2;i<size+2;++i)
for(int j=2;j<size+2;++j)
b[i][j]=OK;
b[xf+2][yf+2]=VISITED;
b[xt+2][yt+2]=TARGET;
cout<<go(b,xf+2,yf+2)<<endl;
}
return 0;
}

No comments:

Post a Comment