http://acm.pku.edu.cn/JudgeOnline/problem?id=1915发现用vector来做宽搜的队列,要比自己弄一个队列来记录方便得多,呵呵
程序很简单,关键地方我都注释上了
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; // 灵活应用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; //初识设置索引是0
index=0;
memset(minMoves,-1,sizeof(minMoves)); //设置所有点未走过
minMoves[beginX][beginY]=0; //设置起点已走过,步数是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;
}