2 #include<queue>
  3 #include<stack>
  4 using namespace std;
  5 //===================================================================
  6 int maze[5][5];
  7 bool mark[5][5];
  8 struct Point 
  9 {
 10     int x,y;
 11 };
 12 
 13 int dir[4][2]={0,1,0,-1,1,0,-1,0};
 14 Point dis[5][5];
 15 stack<Point> S;
 16 int map[5][5];//第三种记录方法
 17 //=====================================================================
 18 
 19 bool InMap(int i,int j)
 20 {
 21     if(i>=0&& i<=4 && j>=0 && j<=4) return true;
 22     else return  false;
 23 }
 24 
 25 void func(int i, int j)
 26 {
 27     if(i==0 && j==0)
 28     {
 29          printf("(0, 0)\n");
 30          return ;
 31     }
 32     Point t;
 33     t.x=i;
 34     t.y=j;
 35     S.push(t);
 36     func(dis[i][j].x,dis[i][j].y);    //递归放入栈，不知道怎么倒序输出
 37 
 38 }
 39 
 40 /*方法二===================================================*/
 41 //void dfs(int x,int y)
 42 //{
 43 //    int pre_x=dis[x][y].x;
 44 //    int pre_y=dis[x][y].y;
 45 //    //如果有祖先，则搜索祖先
 46 //    if(pre_x!=-1 && pre_y!=-1)
 47 //        dfs(pre_x,pre_y);
 48 //    //输出自己的地址，无论是否有祖先(队列中无祖先的只有【0】【0】点）
 49 //    printf("(%d, %d)\n",x,y);
 50 //}
 51 
 52 /*方法三===================================================*/
 53 //void print(int i,int j)
 54 //{
 55 //   if(i==0 && j==0)
 56 //   {
 57 //       printf("(0, 0)\n");
 58 //       return ;
 59 //   }
 60 //
 61 //   print(map[i][j]/5,map[i][j]%5);//先遍历祖先
 62 //   printf("(%d, %d)\n",i,j);
 63 //}
 64 
 65 /*方法四===================================================*/
 66 void print(int i,int j)
 67 {
 68    if(i==0 && j==0)
 69    {
 70        printf("(0, 0)\n");
 71        return ;
 72    }
 73 
 74    print(dis[i][j].x,dis[i][j].y);//先遍历祖先,这两句话的位置很重要，先到祖先，在写自己（下一句话），第一次的错误就是两句话反了
 75     //导致顺序颠倒了
 76    printf("(%d, %d)\n",i,j); 
 77 }
 78 
 79 
 80 void BFS()
 81 {
 82     queue<Point> Q;
 83 
 84     Point cur,m,q;
 85     cur.x=0;
 86     cur.y=0;
 87     mark[0][0]=1;
 88     Q.push(cur);
 89     dis[0][0].x=0;
 90     dis[0][0].y=0;
 91     int xt,yt;
 92 
 93     while(!Q.empty())
 94     {
 95         m=Q.front();
 96         Q.pop();
 97 
 98         for(int i=0;i<4;i++)
 99         {
100             xt=m.x+dir[i][0];
101             yt=m.y+dir[i][1];
102             if(xt==4 && yt==4) 
103             {
104                // func(m.x,m.y);//方法一：放入栈
105                 //dfs(m.x,m.y);//方法二：用深搜
106                 //map[xt][yt]=m.x*5+m.y;//方法三： 用横竖法（自己起的名字），来记录上一次的位置
107                 dis[4][4].x=m.x;
108                 dis[4][4].y=m.y;
109                 print(4,4);
110                 return ;
111             }
112             if(InMap(xt,yt) && mark[xt][yt]==0 && maze[xt][yt]==0)//判断下面一层的结点是否符合
113             {
114 
115                 dis[xt][yt].x=m.x;//记录每上次的结点，这样才可以把整个拎起来
116                 dis[xt][yt].y=m.y;//用dis[][]点来记录每个节点的父节点，因为遍历过就会mark=1,所以只会有一个父节，不会被覆盖
117 
118                 //map[xt][yt]=m.x*5+m.y;//记录路径的好方法！！记录前驱
119 
120                 mark[xt][yt]=1;//访问过后
121                 q.x=xt;
122                 q.y=yt;
123                 Q.push(q);
124 
125             }
126         }
127     }
128 }
129 
130 
131 
132 int main()
133 {
134     int i,j;
135 
136     freopen("in.txt","r",stdin);
137     for(i=0;i<5;i++)
138         for(j=0;j<5;j++)
139             scanf("%d",&maze[i][j]);
140 
141     BFS();
142 
143     //print(4,4);
144     //while(!S.empty())//打印路径
145     //{
146     //    printf("(%d, %d)\n",S.top().x,S.top().y);
147     //    S.pop();
148     //}
149     //printf("(4, 4)\n");
150 
151 
152 
153 
154 
155 
156 }

刚学搜索，总是不开窍，看了介绍，自己磨了两小时才写出来。后面会有DFS和改进后的方法。想通过这道水题，把搜索入了门先。
蓝桥大赛还有几天，再看看，自己水死了。
自己的代码：  1 #include<iostream>

  2 #include<queue>
  3 #include<stack>
  4 using namespace std;
  5 //===================================================================
  6 int maze[5][5];
  7 bool mark[5][5];
  8 struct Point 
  9 {
 10     int x,y;
 11 };
 12 
 13 int dir[4][2]={0,1,0,-1,1,0,-1,0};
 14 Point dis[5][5];
 15 stack<Point> S;
 16 int map[5][5];
 17 //=====================================================================
 18 
 19 bool InMap(int i,int j)
 20 {
 21     if(i>=0&& i<=4 && j>=0 && j<=4) return true;
 22     else return  false;
 23 }
 24 
 25 void func(int i, int j)
 26 {
 27     if(i==0 && j==0)
 28     {
 29          printf("(0, 0)\n");
 30          return ;
 31     }
 32     Point t;
 33     t.x=i;
 34     t.y=j;
 35     S.push(t);
 36     func(dis[i][j].x,dis[i][j].y);    //递归放入栈，不知道怎么倒序输出
 37 
 38 }
 39 
 40 void BFS()
 41 {
 42     queue<Point> Q;
 43 
 44     Point cur,m,q;
 45     cur.x=0;
 46     cur.y=0;
 47     mark[0][0]=1;
 48     Q.push(cur);
 49     dis[0][0].x=0;
 50     dis[0][0].y=0;
 51     int xt,yt;
 52 
 53     while(!Q.empty())
 54     {
 55         m=Q.front();
 56         Q.pop();
 57 
 58         for(int i=0;i<4;i++)
 59         {
 60             xt=m.x+dir[i][0];
 61             yt=m.y+dir[i][1];
 62             if(xt==4 && yt==4) 
 63             {
 64                 func(m.x,m.y);//放入栈
 65                 return ;
 66             }
 67             if(InMap(xt,yt) && mark[xt][yt]==0 && maze[xt][yt]==0)//判断下面一层的结点是否符合
 68             {
 69 
 70                 dis[xt][yt].x=m.x;//记录每上次的结点，这样才可以把整个拎起来
 71                 dis[xt][yt].y=m.y;//用dis[][]点来记录每个节点的父节点，因为遍历过就会mark=1,所以只会有一个父节，不会被覆盖
 72                 mark[xt][yt]=1;//访问过后
 73                 q.x=xt;
 74                 q.y=yt;
 75                 Q.push(q);
 76 
 77             }
 78         }
 79     }
 80 }
 81 
 82 int main()
 83 {
 84     int i,j;
 85 
 86     //freopen("in.txt","r",stdin);
 87     for(i=0;i<5;i++)
 88         for(j=0;j<5;j++)
 89             scanf("%d",&maze[i][j]);
 90 
 91     BFS();
 92 
 93     while(!S.empty())//打印路径
 94     {
 95         printf("(%d, %d)\n",S.top().x,S.top().y);
 96         S.pop();
 97     }
 98     printf("(4, 4)\n");
 99 
100 
101 
102 
103 
104 
105 }

 2 using namespace std;
 3 //==========================================================================
 4 int a[2][100];
 5 int f[2][100];
 6 int t[2][100];
 7 int line[2][100];
 8 int e[2];
 9 int x[2];
10 int lend,fend;
11 //==========================================================================
12 void  FastWay(int a[2][6],int t[2][5],int e[2],int x[2],int n,int &fend,int &lend)
13 {
14      f[0][0] = e[0] + a[0][0];
15     f[1][0] = e[1] + a[1][0];
16     cout << a[0][1] << endl;
17     cout << a[1][1] << endl;
18     for (int j = 1; j < n; j++)
19     {
20         if (f[0][j-1] + a[0][j] <= f[1][j-1] + t[1][j-1] + a[0][j])
21         {
22             f[0][j] = f[0][j-1] + a[0][j];
23             line[0][j] = 0;
24         }
25         else
26         {
27             f[0][j] = f[1][j-1] + t[1][j-1] + a[0][j];
28             line[0][j] = 1;
29         }
30         if (f[1][j-1] + a[1][j] <= f[0][j-1] + t[0][j-1] + a[1][j])
31         {
32             f[1][j] = f[1][j-1] + a[1][j];
33             line[1][j] = 1;
34         }
35         else
36         {
37             f[1][j] = f[0][j-1] + t[0][j-1] + a[1][j];
38             line[1][j] = 0;
39         }
40     }
41     if (f[0][n-1] + x[0] <= f[1][n-1] + x[1])
42     {
43         fend = f[0][n-1] + x[0];
44         lend = 0;
45     }
46     else
47     {
48         fend = f[1][n-1] + x[1];
49         lend = 1;
50     }
51 
52 }
53 
54 //===============================================================================================
55 void PrintStations(int line[2][6],int lend, int n)
56 {
57     int i=lend;
58     cout<<"Line "<<i<<" Station "<<n<<endl; 
59     for(int j=n-1;j>=2;j--)
60     {
61         i=line[i][j];//?????????????????/
62         cout<<"Line "<<i<<" Station "<<j-1<<endl; 
63     }
64 }
65 //===============================================================================================
66 int main()
67 {
68     int n=6;
69     int e[3]={2,4};
70     int x[3]={3,2};
71     int a[2][6]={7,9,3,4,8,4,8,5,6,4,5,7};
72     int t[2][5]={2,3,1,3,4,2,1,2,2,1};
73 
74     int Line[2][6];
75     int LastFlag;
76     int fend;
77 
78      FastWay(a, t, e, x, n,fend,LastFlag);
79     printf("fast = %d;\n", fend);
80     
81     PrintStations(Line, LastFlag, n);
82     return 0;
83 
84 }

 1 //解法一：自己的解法：先求每一行中从i到j的和存储在sum[r]中r从1到n,记录每一列从i到j的和。然后用
 2 //    一维数组的方法求出。47MS。
 3 #include<iostream>
 4 using namespace std;
 5 //=============================================
 6 #define N 102
 7 int p[N][N];
 8 int b[N][N];
 9 #define M 128;
10 int sum[N];
11 //==============================================
12 int Maxtri(int start,int end,int *a)//一维数组求最大子段和
13 {
14     int s=0;int max=-M;
15     for(int i=start;i<=end;++i)
16     {
17         if(s+a[i]>0)
18         {
19             s=s+a[i];
20         }
21         else
22         {
23             s=0;
24         }
25         if(s>max)max=s;
26     }
27     return max;
28 }
29 
30 int main()
31 {
32     int n;
33     int m=-M;
34     cin>>n;
35     for(int i=1;i<=n;++i)
36     {
37         for(int j=1;j<=n;++j)
38         {
39             cin>>p[i][j];
40         }
41     }
42     for(int i=1;i<=n;++i)
43     {
44         for(int j=i;j<=n;++j)
45         {
46             for(int r=1;r<=n;++r)
47             {
48                 sum[r]=0;//勿忘，每次都初始化。。。
49                 for(int k=i;k<=j;++k)
50                 {
51                     sum[r]+=p[r][k];
52                 }
53             }
54             if(Maxtri(1,n,sum)>m)m=Maxtri(1,n,sum);
55         }
56     }
57     cout<<m<<endl;
58 }
59 

  1 /*最大子序和问题，从左到右和从右到左用了不同的方法
  2 求从右到左时我用了
  3     for(int i=0;i<n;++i)
  4     {
  5         if(b+p[i]>0)
  6         {
  7             b=b+p[i];
  8         }
  9         else
 10         {
 11             b=0;
 12         }
 13         if(b>max)max=b;
 14     }
 15     cout<<max<<endl;
 16 这个方法。而从右到左求时，用这方法时
 17 如下
 18         sum2[n-1]=0;
 19         for(int i=n-1;i>=1;--i)
 20        {
 21            if(sum2[i+1]+p[i]>0)
 22            {
 23                sum2[i]=sum2[i+1]+p[i];
 24            }
 25            else
 26            {
 27                sum2[i]=0;
 28            }
 29            if(sum2[i]>max)max=sum2[i];
 30            一直W。。TAT.不知为何.所以换了个方法如下。
 31 主要思路：两个不相交字串，一个从左到右求出sum1[i]为右边前i个数中最大字串（未必从第一个开始，也未必最后一个结束，的任意子串），
 32 而从这时的i到n中求出最大子串值和其相加时，未必为最大和。所以先保证从右到左为最大，求出i，再从i到1求出。
 33 再从和中挑出最大的，若两个都挑出最大的，用函数的话会超时很惨的。*/
 34 
 35 #include<iostream>
 36 #include<stdio.h>
 37 using namespace std;
 38 //=====================================================
 39 #define M 50001
 40 int k;
 41 int p[M],sum1[M],sum2[M];
 42 //=====================================================
 43 int main()
 44 {
 45     int n;
 46     int max=-M;
 47     // freopen( "in.txt", "r", stdin);
 48     //freopen( "out.txt", "w+", stdout); 
 49    scanf("%d",&k);
 50    while(k--)
 51    {
 52        int n;
 53        scanf("%d",&n);
 54 
 55        int max=-M;
 56        int m=-M;
 57        scanf("%d",&p[0]);
 58      
 59       sum1[0]=p[0];
 60     
 61 
 62       for(int i=1;i<n;++i)
 63       {
 64            scanf("%d",&p[i]);
 65            if(sum1[i-1]+p[i]>0)
 66            {
 67                sum1[i]=sum1[i-1]+p[i];
 68            }
 69            else
 70            {
 71                sum1[i]=0;
 72            }
 73        }
 74        sum2[n-1]=p[n-1];
 75        for(int i=n-1;i>=1;--i)
 76        {
 77            if(sum2[i]>0)
 78            {
 79                sum2[i-1]=sum2[i]+p[i-1];
 80            }
 81            else
 82            {
 83                sum2[i-1]=p[i-1];
 84            }
 85            if(sum2[i]>max)max=sum2[i];
 86 
 87            if(sum1[i-1]+max>m)
 88            {
 89                m=sum1[i-1]+max;
 90            }
 91         }
 92         printf("%d\n",m);
 93    }
 94 }
 95      
 96        
 97 
 98 
 99 
100 
101      
102        
103 
104 

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 //================================================
 5 string str1,str2;
 6 int c[1000][1000];//c[i][j]表示到x中的第i个和y中的第j个的已有最长字串的长度
 7 int max(int a,int b)
 8 {
 9     return (a>b?a:b);
10 }
11 int main()
12 {
13     while(cin>>str1>>str2)
14     {
15        //int counter=0;二货！！！！！！！！！！！
16         memset(c,0,sizeof(c));
17         int s1=str1.size();
18         int s2=str2.size();
19         //for(int i=0;i<s1;++i) c[i][0]=0;二货！！字符串时str[0]也是有用的！！
20         //for(int j=0;j<s2;++j) c[0][j]=0;
21         for(int i=1;i<=s1;++i)
22         {
23             for(int j=1;j<=s2;++j)
24             {
25                 if(str1[i-1]==str2[j-1])//处理字符串时又不能从一开始的时候，可以在判断的时候迂回一下
26                 {
27                     c[i][j]=c[i-1][j-1]+1;//通过上一个表示自己，i和j在c[i][j]表示个数时都为加一以后所负责表示。
28                 }
29                 else
30                 {
31                     c[i][j]=max(c[i-1][j],c[i][j-1]);
32                 }
33             }
34         
35         }
36        cout<<c[s1][s2]<<endl;//通过最后递推结果来说明。
37     }
38 }
39 

 1 #include<iostream>
 2 using namespace std;
 3 //===================================================
 4 int k;
 5 struct Point 
 6 {
 7     int a[2][2];
 8     void init()
 9     {
10         a[0][0]=1;a[0][1]=1;
11         a[1][0]=1;a[1][1]=0;
12     }
13 };
14 
15 Point mul(Point p,Point q)//矩阵相乘
16 {
17     int i,j;
18     Point c;
19     for(i=0;i<2;++i)
20     {
21         for(int j=0;j<2;++j)
22         {
23             int sum=0;
24             for(int k=0;k<2;++k)
25             {
26                 sum+=(p.a[i][k]*q.a[k][j])%10000;
27             /*    if(sum>10000)
28                 {
29                     sum-=10000;
30                 }*/
31                 c.a[i][j]=sum%10000;
32             }
33         }
34      }
35     return c;
36 }
37 
38 Point maxtrimul(Point s,int k)
39 {
40     Point ans;
41     ans=s;
42     if(k==1)return s;
43     ans=maxtrimul(s,k>>1);
44     ans=mul(ans,ans);
45     if(k&1)
46     {
47         ans=mul(s,ans);//切记！！！！
48     }
49     return ans;
50     
51 
52 }
53 
54 int main()
55 {
56     Point s;
57     s.init();
58     Point c;
59     while(cin>>k&&k!=-1)
60     {
61         if(k==0)
62         {
63             cout<<0<<endl;
64             continue;
65         }
66         if(k==1)
67         {
68             cout<<1<<endl;
69             continue;
70         }
71         c=maxtrimul(s,k);
72         cout<<(c.a[0][1]%10000)<<endl;
73         continue;
74 
75     }
76 }

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 //======================================================
 5 struct Point
 6 {
 7     int x;int y;
 8     int flag;
 9 };
10 struct Point p[50050];
11 int n;
12 //======================================================
13 //原来自己用了两方面即想x相同时比y,y相同时比x，两个排序，两个比较，超时。没有下面方法好，只用了一半。。。要好好加油了~TVT.
14 //按照x从小到大排序，当x相等时按照y从大到小排序,从左到右，见到最高的就加一,counter初始值为1
15 //即x最大时，y中也是最大值的p[n-1].y一定是，然后就像爬楼梯一样比较
16 int cmp1( const void *a , const void *b )
17 {
18     struct Point *c = (Point *)a;
19     struct Point *d = (Point *)b;
20     if(c->x != d->x) return c->x - d->x;
21     else return c->y - d->y;
22 }
23 
24 
25 //==============================================================
26 int main()
27 {
28 
29     while(scanf("%d",&n)!=EOF&&n)
30     {
31         int counter=1;
32         memset(p,0,sizeof(p));
33         for(int i=0;i<n;++i)
34         {
35             cin>>p[i].x>>p[i].y;
36         }
37         qsort(p,n,sizeof(p[0]),cmp1);//按照x从小到大排序，当x相等时按照y从大到小排序
38         //从左到右，见到最高的就加一
39         int max=p[n-1].y;
40         for(int i=n-2;i>=0;--i)
41         {
42             if(p[i].y>max)
43             {
44                 counter++;
45                 max=p[i].y;
46             }
47         }
48         printf("%d\n",counter);
49     }
50     
51 }