poj 3984 bfs+栈的使用 博客分类: acm c++acm
程序员文章站
2024-02-18 23:37:10
...
#include <stdio.h> #include <algorithm> #include <string.h> #include <queue> #include <stack> using namespace std; int dir[]={-1,0,1,0}; int dil[]={0,-1,0,1}; int num[6][6]; int visit[6][6]; int d[30]; struct node { int x,y,id; }a[30]; int cet; void bfs() { queue<node>q; cet = 0; a[cet].x = 0; a[cet].y = 0; a[cet].id = 0; d[0]=-1; q.push(a[cet]); bool flag = true; while(!q.empty()&&flag) { node xx = q.front(); int t = xx.id; q.pop(); visit[xx.x][xx.y] = true; for(int k=0;k<=3;k++) { int p = xx.x+dir[k]; int v = xx.y+dil[k]; if(!visit[p][v]&&num[p][v]!=1&&p>=0&&p<5&&v>=0&&v<5) { cet++; d[cet] = t; a[cet].x = p; a[cet].y = v; a[cet].id = cet; q.push(a[cet]); if(a[cet].x==4&&a[cet].y==4) { flag = false; break; } } } } } int main() { for(int i=0;i<5;i++) { for(int j=0;j<5;j++) { scanf("%d",&num[i][j]); visit[i][j] = false; } } memset(d,-1,sizeof(d)); bfs(); stack<node>st; while(cet>=0) { st.push(a[cet]); cet=d[cet]; } while(!st.empty()) { node ll = st.top(); printf("(%d, %d)\n",ll.x,ll.y); st.pop(); } return 0; }