ACM.zip_visual c

/* hdoj 1242 ac time 2012.7.7 2:48 ps:第一次用c++ STL标签，第一次知道和怎么用广度优先的队列表示形式，还有优先队列 by hhz */ #include <stdio.h> #include <stdlib.h> #include <iostream> #include <queue> using namespace std; struct node //存入队列的结构体 { int x, y,count; friend bool operator < (node a, node b) //优先队列中 优先级的判断 { //表示count小的权值大 return a.count > b.count; } }; int dir[][2]={{1,0},{0,1},{-1,0},{0,-1}}; char matrix[202][202]; bool flag; int S_x=0,S_y=0,E_x,E_y,m,n; node cur,next; //cur表示正处于的结点，并且得取出，从队列里剔除，next是上下左右遍历到，将要存入列队的结点 int bfs() { int i,gox,goy; priority_queue<node> q; //定义队列q cur.x=S_x; cur.y=S_y; cur.count=0; q.push(cur); //放入开始起点的结点 while(!q.empty()){ //循环判定条件时队列不为空时 cur=q.top(); //先将第一个结点取出，放到cur中，再从队列中剔除 q.pop(); for(i=0;i<4;i++){ gox=cur.x+dir[i][0]; goy=cur.y+dir[i][1]; if(gox>=0 && gox<m && goy>=0 && goy<n){ if(matrix[goy][gox]!='#'){ next.x=gox; //将满足的点存到next结点中，并按照条件赋值count，再存入队列中 next.y=goy; if(matrix[goy][gox]=='x'){ next.count=cur.count+2; q.push(next); matrix[goy][gox]='#'; //printf("x %d %d %d\n",gox,goy,next.count); }else if(matrix[goy][gox]=='.'){ next.count=cur.count+1; q.push(next); matrix[goy][gox]='#'; //printf(". %d %d %d\n",gox,goy,next.count); }else if(matrix[goy][gox]=='r'){ cur.count=cur.count+1; flag=true; return 1; } } } } } } int main() { int i,j,wall=0; while(scanf("%d%d\n",&n,&m)!=EOF){ int wall=0; for(i=0;i<n;i++){ for(j=0;j<m;j++){ scanf("%c",&matrix[i][j]); if(matrix[i][j]=='#') wall++; if(matrix[i][j]=='a'){ S_x=j; S_y=i; } if(matrix[i][j]=='r'){ E_x=j; E_y=i; } } getchar(); } if(wall+abs(S_x-E_x)+abs(S_y-E_y)+1>n*m) printf("Poor ANGEL has to stay in the prison all his life.\n"); else{ flag=false; bfs(); if(flag==true) printf("%d\n",cur.count); else printf("Poor ANGEL has to stay in the prison all his life.\n"); flag=false; memset(matrix,0,sizeof(matrix)); //清零的方法，很好用 } } } /* 题目大意:一个矩阵，是一个监狱，有墙，有路，天使在里面，还有她的同伴，只要她的同伴找到了她，她就能获救，同伴不止一个 而且重点在于，中间还有一个叫做门卫的东西，当同伴遇到他时，得先干掉他，干掉他得花去1步的代价。可以走上下左右四个方向 最后输出最小的步数。 思路:首先求最小步数，很显然想到bfs（原因可见hdo1240）。解决问题的关键就在于有不止一个的同伴以及门卫了。 刚开始傻逼，被题目蒙蔽了，只以同伴为中心，想着有几个同伴依次拿这么多个同伴为起点，多次进行bfs，最后看步数最小的。 但是太耗时间了。聪明的想法是，天使只有一个，以天使为起点，当以bfs找到第一个同伴时，即可结束，而且步数是最小的。 然后就是门卫的问题了。刚开始我想到了，只要碰到门卫，就在那个地点再待一回合，等于那个点遍历了两次。但纠结这样会不会 妨碍到其它点的遍历，其实是想多了，bfs，每一个树层，步数都是相同的，在第一次到门卫这个点时，它的子节点只有一个，就是它自己 然后再以与他相连接的节点往下遍历其它点。这不会影响其它点的遍历的。好，接下来思考实现过程。 本程序用了STL标签中的优先队列priority_queue<node> q; 之前定义的 首先讲队列，我们用bfs 时，处于哪个点，也就是说现在到了这个点，将要进行它4个方向的遍历了，开始先把此点从队列取出 存放到cur这个结构体中。 即 cur=q.top() (top就是队列最前面将要出来的点)然后再把它释放掉 q.pop() (pop就是把最开始的点从队列中剔除) 接着，以cur里面的坐标为中心，遍历上下左右4个方向 。当遍历的点满足条件时，则用next这个结构体来保存它的坐标，再进行判断是 .还是x还是r 。然后再存对应的count ，左后把此结点放到队列中，即q.push(next) .为了表示此点已经遍历，这将其值改为# 墙 friend bool operator < (node a, node b) { return a.count > b.count; } 此队列以count的权值作为优先条件，在所有队列中，优先使count小的结点先出队列，也就是q.pop() q.top()时，都是count小的先出 普通情况下，我们没走一步，count加1，也就是树层结构每一层都对应count,每加一层,count +1。但是 当遇到X(门卫)时，就让它count+2,这样，此点就处于队列的尾部了，也就是说我们先遍历完之前count+1的点后，再遍历它，正好就代表了 这个结点的下一个结点是自己的这种图的结构（结合队列及树的结构，画画就知道了） memset(matrix,0,sizeof(matrix)); 表示将matrix数组的所有数值全变为0,精辟在于 sizeof(matrix)，即为它的长度，很有用 PS:bfs是对内 dfs是栈，用队列的话可以形象，简单的把搜索进行到底，但是相比较之前的用标志h,t以及数组存储每个结点存放的坐标 状态，它就不能对号入座了，即如果之后翻过来查看之前每个点的一些信息，就搞不定了。 ca，明天，哦不对，是今天日子不好过啊，得被那个SB老师批斗了...得装怂，恩恩... hhz 2012.7.7 3:16 */