POJ2790解题报告

2790:迷宫描述一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n*n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。输入第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n(1=n=100)，表示迷宫的规模是n*n的。接下来是一个n*n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha,la,hb,lb，描述A处在第ha行,第la列，B处在第hb行,第lb列。注意到ha,la,hb,lb全部是从0开始计数的。输出k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。样例输入23.##..##..00225.....###.#..#..###.....#.0040样例输出YESNO解题思路：利用深度优先的方法找到第一个可行的路径具体步骤：1、使用一个栈来寄存待回溯访问的结点；2、判断首结点是否满足条件，若满足则入栈，若否则直接返回；3、试探下一个可以访问的结点（满足可访问且没有重复访问过）；4、若存在可以访问的结点：4.1、访问第一个可以访问的结点；4.2、访问时，将结点入栈并标记，以便判断重复访问性；4.3、对访问的结点考察步骤3；5、若不存在可以访问的结点：5.1、退栈，然后对栈顶结点考察步骤3；6、当退栈至首结点，且无法继续访问时，返回结果NO；7、当访问到目标结点时，返回结果YES。C++代码：#includeiostream#includestack#includevector#ifndefMAX#defineMAX101#endifusingnamespacestd;classcor{public:intx;inty;};intmain(){stackcorpath;cornode{0,0};intk;cink;for(inti=0;ik;i++){intn;cinn;charmaze[MAX][MAX];for(inti=0;in;i++){for(intj=0;jn;j++){cinmaze[i][j];}}intha,la,hb,lb;cinhalahblb;node.x=ha;node.y=la;path.push(node);boolflag=false;while(true){if(maze[node.x][node.y]=='#'){break;}if(node.x==hb&&node.y==lb){flag=true;coutYESendl;break;}//toleftif(node.x-1=0&&maze[node.x-1][node.y]=='.'){node.x--;maze[node.x][node.y]='$';path.push(node);continue;}//torightif(node.x+1n&&maze[node.x+1][node.y]=='.'){node.x++;maze[node.x][node.y]='$';path.push(node);continue;}//toupif(node.y-1=0&&maze[node.x][node.y-1]=='.'){node.y--;maze[node.x][node.y]='$';path.push(node);continue;}//todownif(node.y+1n&&maze[node.x][node.y+1]=='.'){node.y++;maze[node.x][node.y]='$';path.push(node);continue;}path.pop();if(path.empty()){break;}node=path.top();}if(!flag)coutNOendl;}return0;}