Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
路径输出是坎,听学长讲讲了一小时,再花了一个多小时,终于过了。。。特们的,为何可以水过#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <queue> using namespace std; struct Node { int x,y; }node[30]; int father[30],map[5][5],vis[5][5]; int xx[4]={1,-1,0,0}; int yy[4]={0,0,1,-1}; queue<Node>q; void printf_1() { int a[30]; //printf("(0, 0)\n"); int u=24; int j=0; while(1) { a[j++]=father[u]; u=father[u]; if(u==0) break; } //printf("(0, 0)\n"); for(int i=j-1;i>=0;i--) printf("(%d, %d)\n",a[i]/5,a[i]%5); printf("(4, 4)\n"); } void bfs(int x,int y) { memset(vis,0,sizeof(vis)); memset(father,-1,sizeof(father)); vis[0][0]=1; Node now,next; now.x=0,now.y=0; //father[x*5+y]=0; q.push(now); while(!q.empty()) { now=q.front(); q.pop(); for(int i=0;i<4;i++) { int dx=now.x+xx[i]; int dy=now.y+yy[i]; if(dx>=0&&dx<=4&&dy>=0&&dy<=4&&vis[dx][dy]==0&&map[dx][dy]==0) { vis[dx][dy]=1; father[dx*5+dy]=now.x*5+now.y; if(dx==4&&dy==4) { printf_1(); return ; } next.x=dx; next.y=dy; q.push(next); } } } } int main () { for(int i=0;i<=4;i++) for(int j=0;j<=4;j++) scanf("%d",&map[i][j]); bfs(0,0); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator