最少拐弯(广搜)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int dx[]={0,1,0,-1};
 4 int dy[]={1,0,-1,0};
 5 struct sj
 6 {
 7     int x,y,turn;
 8 }s,t,p;
 9 queue<sj> q;
10 int n,m,c[101][101];
11 bool v[101][101];
12 int main()
13 {
14     cin>>n>>m;
15     for(int i=1;i<=n;i++)
16         for(int j=1;j<=m;j++)
17             cin>>c[i][j];
18     cin>>s.x>>s.y>>t.x>>t.y;
19     q.push(s);
20     memset(v,0,sizeof(v));
21     q.front().turn=0;
22     while(!q.empty())
23     {
24         for(int i=0;i<4;i++)
25         {
26             p.x=q.front().x+dx[i];
27             p.y=q.front().y+dy[i];
28              while(p.x>0&&p.x<=n&&p.y>0&&p.y<=m&&!c[p.x][p.y])
29             {
30                 if(!v[p.x][p.y])
31                 {
32                     if(p.x==t.x&&p.y==t.y)
33                     {
34                         printf("%d\n",q.front().turn);
35                         return 0;
36                     }
37                     v[p.x][p.y]=1;
38                     p.turn=q.front().turn+1;
39                     q.push(p);
40                 }
41                 p.x+=dx[i];
42                 p.y+=dy[i];
43             }
44         }
45         q.pop();
46     }
47     return 0;
48 }

 

上一篇:【ACwing 1017 怪盗基德的滑翔翼】线性dp->最长上升子序列模型


下一篇:一些函数使用上的问题