题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1010
古人云：“由简入奢易,由奢入简难”，咱写代码也是一样，不求最快，但求最繁，繁得让你都不忍读完它。。。。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class postion
{//位置类
public:
postion(int r=0,int c=0):row(r),col(r)
{
}
void setRow(int r)
{
row = r;
}
void setCol(int c)
{
col = c;
}
int getRow()const
{
return row;
}
int getCol()const
{
return col;
}
postion& operator =(const postion& rhs)
{
row = rhs.row;
col = rhs.col;
level = rhs.level;
return *this;
}
bool operator ==(const postion& rhs)const
{
if(row==rhs.row&&col==rhs.col)
return true;
else
return false;
}
void setLevel(int lev)
{
level = lev;
}
int getLevel()const
{
return level;
}
private:
int row;
int col;
int level;//所处的层次
};
typedef queue<postion, deque<postion, allocator<postion> > > POSTION_QUEUE;
template<typename T>
class Matrix
{//矩阵类
public:
Matrix(int nR=0,int nC=0,int tm=0)
{
nRows = nR;
nCols = nC;
timeout = tm;
initMat();//初始化矩阵
}
vector<T>& operator [] (int nR)
{//重载[]操作符
return data[nR];
}
void setStartPos(int r,int c)
{//设置起始点
start.setRow(r);
start.setCol(c);
start.setLevel(0);
}
void setExitPos(int r,int c)
{//设置出口点
exit.setRow(r);
exit.setCol(r);
}
bool isPosOK(const postion& curPos,postion& desPos,int type)
{
int curRow = curPos.getRow();//当前行
int curCol = curPos.getCol();//当前列
switch(type)
{
case 0://东面
{
if(data[curRow][curCol+1]!='X' && visited[curRow][curCol+1]==false)
{
desPos.setRow(curRow);
desPos.setCol(curCol+1);
return true;
}
break;
}
case 1://南面
{
if(data[curRow+1][curCol]!='X' && visited[curRow+1][curCol]==false)
{
desPos.setRow(curRow+1);
desPos.setCol(curCol);
return true;
}
break;
}
case 2://西面
{
if(data[curRow][curCol-1]!='X' && visited[curRow][curCol-1]==false)
{
desPos.setRow(curRow);
desPos.setCol(curCol-1);
return true;
}
break;
}
case 3://北面
{
if(data[curRow-1][curCol]!='X' && visited[curRow-1][curCol]==false)
{
desPos.setRow(curRow-1);
desPos.setCol(curCol);
return true;
}
break;
}
default:
break;
}
return false;
}
void escape()
{//BFS算法来从迷宫中逃出，不懂啥剪枝不剪枝。。。
POSTION_QUEUE qRoad;
start.setLevel(0);//起始点在第0层
qRoad.push(start);
postion curPos;
postion desPos;//下一个目标点
int i;
int curLev = 0;
while(!qRoad.empty())
{
curPos = qRoad.front();
curLev = curPos.getLevel();//获取当前所处层次
if(curPos==exit&&curLev<=timeout)
{//达到出口点了，ok,mission over
cout<<"YES"<<endl;
return;
}
int row = curPos.getRow();
int col = curPos.getCol();
visited[row][col] = true;//当前位置标记为已经访问过了
for(i=0;i<4;i++)
{
if(i==0&&col==nCols-1)continue;
else if(i==1&&row==nRows-1)continue;
else if(i==2&&col==0)continue;
else if(i==3&&row==0)continue;
else
if(isPosOK(curPos,desPos,i))
{//下一个位置可用
desPos.setLevel(curLev+1);
qRoad.push(desPos);
visited[desPos.getRow()][desPos.getCol()] = true;
}
}
qRoad.pop();
}
cout<<"NO"<<endl;
}
private:
vector<vector<T> > data;//存储数据
vector<vector<bool> > visited;
int nRows;//行数
int nCols;//列数
int timeout;//计时器
postion start;//起始点
postion exit;//出口点
void initMat()
{//真正的初始化矩阵
int i,j;
for(i=0;i<nRows;++i)
{
data.push_back(vector<T>());
visited.push_back(vector<bool>());
for(j=0;j<nCols;++j)
{
data[i].push_back(T());
visited[i].push_back(false);
}
}
}
};
int main()
{
int n,m,t,i,j;
while(cin>>n>>m>>t&&!(n==0&&m==0&&t==0))
{
char tmp;
Matrix<char> maze(n,m,t);
for(i=0;i<n;++i)
for(j=0;j<m;++j)
{
cin>>tmp;
maze[i][j] = tmp;
switch(tmp)
{
case'S':
maze.setStartPos(i,j);//设置起始点
break;
case'D':
maze.setExitPos(i,j);//设置出口点
break;
}
}
maze.escape();
}
return 0;
}
本地测试结果
可惜还是WA,不过实在是想不出来还有什么特别的测试用例没试过了，从起始点开始广度优先搜索，每进下一级子层都记录下所在层次数，在前进的过程中若达到出口，且层次数和时限吻合就成功，思路应该是没错的，看他们都是用的DFS,难道不能用BFS?算了，先记录在此，以后再修改。。
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2007/12/24/1012871.html，如需转载请自行联系原作者
