poj 3984 迷宫问题

 1 
 2
 3    
 4    /*************************************************************************
 5    	> File Name: code/2015summer/searching/KK.cpp
 6    	> Author: 111qqz
 7    	> Email: rkz2013@126.com 
 8    	> Created Time: 2015年07月25日 星期六 13时33分00秒
 9     ************************************************************************/
10    
11    #include<iostream>
12    #include<iomanip>
13    #include<cstdio>
14    #include<algorithm>
15    #include<cmath>
16    #include<cstring>
17    #include<string>
18    #include<map>
19    #include<set>
20    #include<queue>
21    #include<vector>
22    #include<stack>
23    #define y0 abc111qqz
24    #define y1 hust111qqz
25    #define yn hez111qqz
26    #define j1 cute111qqz
27    #define tm crazy111qqz
28    #define lr dying111qqz
29    using namespace std;
30    #define REP(i, n) for (int i=0;i<int(n);++i)  
31    typedef long long LL;
32    typedef unsigned long long ULL;
33    int a[10][10];
34    int head = 0;
35    int tail = 1;
36    int dirx[2]={1,0};
37    int diry[2]={0,1};
38    struct node
39    {
40        int x,y,pre;
41    }q[10];
42    
43    void print(int x)
44    {
45        if (q[x].pre!=-1)
46        {
47    	  print(q[x].pre);
48    	  printf("(%d, %d)\n",q[x].x,q[x].y);
49        }
50    }
51    void bfs()
52    {
53        q[head].x=0;
54        q[head].y=0;
55        q[head].pre=-1;
56        while (head<tail)
57        {
58    	  if (q[head].x==4&&q[head].y==4) 
59    	  {
60    		print(head);
61    		return;
62    	  }
63    	  for (int i = 0 ; i < 2 ; i++ )
64    	  {
65    		int newx=dirx[i]+q[head].x;
66    		int newy=diry[i]+q[head].y;
67    		if (newx>=0&&newx<5&&newy>=0&&newy<5&&a[newx][newy]==0)
68    		{
69    		    q[tail].x=newx;
70    		    q[tail].y=newy;
71    		    q[tail].pre=head;
72    		    tail++;
73    		}
74    	  }
75    	  head++;
76        }
77    
78    }
79    int main()
80    {
81        for ( int i = 0 ; i < 5 ; i++ )
82        {
83    	  for ( int j = 0 ; j < 5;  j++)
84    	  {
85    		cin>>a[i][j];
86    	  }
87        }
88        printf("(0, 0)\n");
89        bfs();
90      
91    	return 0;
92    }
93    
94
95