HDU1010 Tempter of the Bone

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1010

古人云：“由简入奢易,由奢入简难”，咱写代码也是一样，不求最快，但求最繁，繁得让你都不忍读完它。。。。

<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->#include<iostream>
#include<vector>
#include<queue>
usingnamespacestd;

classpostion
{//位置类
public:
postion(intr=0,intc=0):row(r),col(r)
{
}
voidsetRow(intr)
{
row=r;
}
voidsetCol(intc)
{
col=c;
}
intgetRow()const
{
returnrow;
}
intgetCol()const
{
returncol;
}
postion&operator=(constpostion&rhs)
{
row=rhs.row;
col=rhs.col;
level=rhs.level;
return*this;
}
booloperator==(constpostion&rhs)const
{
if(row==rhs.row&&col==rhs.col)
returntrue;
else
returnfalse;
}
voidsetLevel(intlev)
{
level=lev;
}
intgetLevel()const
{
returnlevel;
}
private:
introw;
intcol;
intlevel;//所处的层次
};

typedefqueue<postion,deque<postion,allocator<postion>>>POSTION_QUEUE;

template<typenameT>
classMatrix
{//矩阵类
public:
Matrix(intnR=0,intnC=0,inttm=0)
{
nRows=nR;
nCols=nC;
timeout=tm;
initMat();//初始化矩阵
}
vector<T>&operator[](intnR)
{//重载[]操作符
returndata[nR];
}
voidsetStartPos(intr,intc)
{//设置起始点
start.setRow(r);
start.setCol(c);
start.setLevel(0);
}
voidsetExitPos(intr,intc)
{//设置出口点
exit.setRow(r);
exit.setCol(r);
}
boolisPosOK(constpostion&curPos,postion&desPos,inttype)
{
intcurRow=curPos.getRow();//当前行
intcurCol=curPos.getCol();//当前列

switch(type)
{
case0://东面
{
if(data[curRow][curCol+1]!='X'&&visited[curRow][curCol+1]==false)
{
desPos.setRow(curRow);
desPos.setCol(curCol+1);
returntrue;
}
break;
}
case1://南面
{
if(data[curRow+1][curCol]!='X'&&visited[curRow+1][curCol]==false)
{
desPos.setRow(curRow+1);
desPos.setCol(curCol);
returntrue;
}
break;
}
case2://西面
{
if(data[curRow][curCol-1]!='X'&&visited[curRow][curCol-1]==false)
{
desPos.setRow(curRow);
desPos.setCol(curCol-1);
returntrue;
}
break;
}
case3://北面
{
if(data[curRow-1][curCol]!='X'&&visited[curRow-1][curCol]==false)
{
desPos.setRow(curRow-1);
desPos.setCol(curCol);
returntrue;
}
break;
}
default:
break;
}
returnfalse;
}
voidescape()
{//BFS算法来从迷宫中逃出，不懂啥剪枝不剪枝。。。
POSTION_QUEUEqRoad;
start.setLevel(0);//起始点在第0层
qRoad.push(start);
postioncurPos;
postiondesPos;//下一个目标点
inti;
intcurLev=0;
while(!qRoad.empty())
{
curPos=qRoad.front();
curLev=curPos.getLevel();//获取当前所处层次
if(curPos==exit&&curLev<=timeout)
{//达到出口点了，ok,missionover
cout<<"YES"<<endl;
return;
}
introw=curPos.getRow();
intcol=curPos.getCol();
visited[row][col]=true;//当前位置标记为已经访问过了

for(i=0;i<4;i++)
{
if(i==0&&col==nCols-1)continue;
elseif(i==1&&row==nRows-1)continue;
elseif(i==2&&col==0)continue;
elseif(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;
intnRows;//行数
intnCols;//列数
inttimeout;//计时器
postionstart;//起始点
postionexit;//出口点
voidinitMat()
{//真正的初始化矩阵
inti,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);
}
}
}

};

intmain()
{
intn,m,t,i,j;
while(cin>>n>>m>>t&&!(n==0&&m==0&&t==0))
{
chartmp;
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();

}
return0;
}

本地测试结果

可惜还是WA,不过实在是想不出来还有什么特别的测试用例没试过了，从起始点开始广度优先搜索，每进下一级子层都记录下所在层次数，在前进的过程中若达到出口，且层次数和时限吻合就成功，思路应该是没错的，看他们都是用的DFS,难道不能用BFS?算了，先记录在此，以后再修改。。