http://acm.pku.edu.cn/JudgeOnline/problem?id=1915發(fā)現(xiàn)用vector來做寬搜的隊列,要比自己弄一個隊列來記錄方便得多,呵呵
程序很簡單,關(guān)鍵地方我都注釋上了
Source Code
Problem: 1915 User: lnmm
Memory: 1560K Time: 156MS
Language: C++ Result: Accepted
Source Code
#include <iostream>
#include <vector>
using namespace std;
int mapSize,beginX,beginY,EndX,EndY;
int minMoves[301][301];
int index;
bool find;
struct point
{
int x;
int y;
}tempPoint;
vector <point> vec; // 靈活應(yīng)用vector.push_back(),即放到隊尾 (比較.push()入棧) ;用index來控制處理順序
void deal(int x,int y,int times)
{
if(x==EndX&&y==EndY)
{
find=true;
return;
}
if(x-2>=0&&y-1>=0&&minMoves[x-2][y-1]==-1) //如果 某種走法沒有超過棋盤界限 且 那一格沒有走過
{
minMoves[x-2][y-1]=times+1;
tempPoint.x=x-2;
tempPoint.y=y-1;
vec.push_back(tempPoint);
}
if(x-2>=0&&y+1<mapSize&&minMoves[x-2][y+1]==-1)
{
minMoves[x-2][y+1]=times+1;
tempPoint.x=x-2;
tempPoint.y=y+1;
vec.push_back(tempPoint);
}
if(x+2<mapSize&&y+1<mapSize&&minMoves[x+2][y+1]==-1)
{
minMoves[x+2][y+1]=times+1;
tempPoint.x=x+2;
tempPoint.y=y+1;
vec.push_back(tempPoint);
}
if(x+2<mapSize&&y-1>=0&&minMoves[x+2][y-1]==-1)
{
minMoves[x+2][y-1]=times+1;
tempPoint.x=x+2;
tempPoint.y=y-1;
vec.push_back(tempPoint);
}
if(x-1>=0&&y-2>=0&&minMoves[x-1][y-2]==-1)
{
minMoves[x-1][y-2]=times+1;
tempPoint.x=x-1;
tempPoint.y=y-2;
vec.push_back(tempPoint);
}
if(x-1>=0&&y+2<mapSize&&minMoves[x-1][y+2]==-1)
{
minMoves[x-1][y+2]=times+1;
tempPoint.x=x-1;
tempPoint.y=y+2;
vec.push_back(tempPoint);
}
if(x+1<mapSize&&y-2>=0&&minMoves[x+1][y-2]==-1)
{
minMoves[x+1][y-2]=times+1;
tempPoint.x=x+1;
tempPoint.y=y-2;
vec.push_back(tempPoint);
}
if(x+1<mapSize&&y+2<mapSize&&minMoves[x+1][y+2]==-1)
{
minMoves[x+1][y+2]=times+1;
tempPoint.x=x+1;
tempPoint.y=y+2;
vec.push_back(tempPoint);
}
}
int main()
{
int nCase;
cin>>nCase;
while(nCase--)
{
cin>>mapSize;
cin>>beginX>>beginY;
cin>>EndX>>EndY;
find=false; //初識設(shè)置索引是0
index=0;
memset(minMoves,-1,sizeof(minMoves)); //設(shè)置所有點未走過
minMoves[beginX][beginY]=0; //設(shè)置起點已走過,步數(shù)是0
vec.clear();
point tempPoint;
tempPoint.x=beginX;
tempPoint.y=beginY;
vec.push_back(tempPoint);
while(index<vec.size()&&!find) //vec里還有元素未處理完 且 沒有找到 vec.size() range from 0 to vex.size-1
{
deal(vec[index].x,vec[index].y,minMoves[vec[index].x][vec[index].y]);
index++;
}
cout<<minMoves[EndX][EndY]<<endl;
}
return 0;
}