[kuangbin带你飞]专题一简单搜索

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 struct node
 8 {
 9     int x;
10     int y;
11     int s;
12 };
13 int g[10][10];
14 int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
15 int main()
16 {
17 //    freopen("in.in","r",stdin);
18     node s, t;
19     string l;
20     queue<node>q;
21     vector<node>v;
22     
23     for(int i = 0; i <= 6; i++)
24         for(int j = 0; j <= 6; j++)
25             g[i][j] = 1;    
26             
27     for(int i = 1; i <= 5; i++)
28         for(int j = 1; j <= 5; j++)
29             scanf("%d",&g[i][j]);        
30 
31     s.x = 1;
32     s.y = 1;
33     s.s = -1;
34     q.push(s);
35     while(q.size())
36     {
37         s = q.front();
38         q.pop();
39         g[s.x][s.y] = s.s;
40         if(s.x == 5 && s.y == 5)    break;
41         
42         for(int i = 0; i < 4; i++)
43         {
44             t.x = s.x + d[i][0];
45             t.y = s.y + d[i][1];
46             t.s = s.s - 1;
47             if(g[t.x][t.y] == 0)
48                 q.push(t);
49 
50         }
51     }
52     while(q.size())    q.pop();
53     s.x = 5;
54     s.y = 5;
55     q.push(s);
56     while(q.size())
57     {
58         s = q.front();
59         q.pop();
60         if(s.x == 1 && s.y == 1)    break;
61         for(int i = 0; i < 4; i++)
62         {
63             t.x = s.x + d[i][0];
64             t.y = s.y + d[i][1];
65             if(g[t.x][t.y] == g[s.x][s.y] + 1)
66             {
67                 q.push(t);
68                 v.push_back(t);
69                 break;
70             }
71         }
72     }
73     for(int i = v.size() - 1; i >= 0; i--)
74         printf("(%d, %d)
",v[i].x-1,v[i].y-1);
75     printf("(4, 4)
");
76     return 0;
77 }
[kuangbin带你飞]专题一 简单搜索

[kuangbin带你飞]专题一简单搜索
