C++博客-Sai

还是POJ3984__BFS【四种记录路径的方法总结】

四也 — Mon, 14 May 2012 15:45:00 GMT

方法一就上一篇最原始的stack保护路径，方法二，三，四（其实一样）是递归回溯深搜路径，只不过存储结构不同，有的很妙，自己的很糟TAT。
后篇将有深搜方法和不用STL做出的。 1 #include<iostream>

  2 #include
  3 #include
  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 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 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 }

四也 2012-05-14 23:45 发表评论

POJ 3984 方法一【BFS+Stack 记录路径】

四也 — Mon, 14 May 2012 15:02:00 GMT

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

四也 2012-05-14 23:02 发表评论

【算法导论】动态规划实现

四也 — Sun, 06 May 2012 13:15:00 GMT

对于 line[6][2]的记录机制还有疑问，等下细细看来，再补上解答 1 #include<iostream>

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 "< 59     for(int j=n-1;j>=2;j--)
60     {
61         i=line[i][j];//?????????????????/
62         cout<<"Line "< 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 }

四也 2012-05-06 21:15 发表评论

POJ 1050 二维最大子矩阵

四也 — Tue, 29 Nov 2011 12:42:00 GMT

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

四也 2011-11-29 20:42 发表评论

POJ 2479 最大子段和问题

四也 — Mon, 28 Nov 2011 14:37:00 GMT

1 /*最大子序和问题，从左到右和从右到左用了不同的方法
  2 求从右到左时我用了
  3     for(int i=0;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< 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

四也 2011-11-28 22:37 发表评论

POJ 1458 最长公共子列

四也 — Sun, 27 Nov 2011 08:34:00 GMT

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;i20         //for(int j=0;j
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

四也 2011-11-27 16:34 发表评论

POJ 3070 这个为矩阵相乘的基础题。

四也 — Sun, 27 Nov 2011 03:54:00 GMT

建议做矩阵相乘时先做3070,后面在开始做3233,3623,2440.3623和2440我还没开始做，今天下午就要自己做出来！！！！还有。。。海贼王更新了！！！！

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 }

四也 2011-11-27 11:54 发表评论

POJ 3233 快速幂和二分。。。基本上是别人的代码，自己改动一些，不过收获很大。

四也 — Sun, 27 Nov 2011 02:58:00 GMT

借鉴http://www.cnblogs.com/ACShiryu/archive/2011/08/09/poj3233.html

1  /* 这道题目借鉴他人的思路和代码，很有收获
  2   先看下面这个快速幂求余的运算
  3 递归用二分法，每个过程都求余。
  4 long exp_mod(long a,long n,long b)
  5 {
  6     long t;
  7     if(n==0) return 1%b;
  8     if(n==1) return a%b;
  9     t=exp_mod(a,n/2,b);
10     t=t*t%b;
11     if((n&1)==1) t=t*a%b;
12     return t;
13 }
14 本题用了两次二分的思想，一次用于求A^K,第二次用于求 (1+A^(k/2))*(A + A^2 + A^3 + … + A^(k/2))
15 */
16
17
18 #include<iostream>
19 #include<stdio.h>
20 using namespace std;
21 //=======================================================
22 int n,m,k;
23 struct Point//定义结构体更加方便,用数组时结构体有大作用的
24 {
25      int a[32][32];
26      void init()
27      {
28          memset(a,0,sizeof(a));
29          for(int i=1;i<=32;++i)
30          {
31              a[i][i]=1;
32          }
33      }
34 };
35 //=======================================================
36 Point mul(Point x,Point y)//乘法运算
37 {
38     Point z;
39     for(int i=1;i<=n;++i)
40     {
41         for(int j=1;j<=n;++j)
42         {
43             int sum=0;
44             for(int k=1;k<=n;++k)
45             {
46                 sum+=((x.a[i][k]*y.a[k][j])%m);//每次都求余
47                 z.a[i][j]=(sum%m);//这时也要求余。。。。。。
48             }
49         }
50     }
51     return z;
52 }
53
54 Point add(Point p,Point q)//矩阵加法运算
55 {
56     Point c;
57     for(int i=1;i<=n;++i)
58     {
59         for(int j=1;j<=n;++j)
60         {
61             c.a[i][j]=((p.a[i][j]+q.a[i][j])%m);//记得求余
62         }
63     }
64     return c;
65 }
66
67 void display(Point p)//打印函数
68 {
69     int i,j;
70     for( i=1;i<=n;++i)
71     {
72         for(j=1;j<=n-1;++j)
73         {
74             cout<<p.a[i][j]<<" ";//注意格式“ ”问题
75         }
76         if(j==n)cout<<p.a[i][j]<<endl;
77
78     }
79 }
80
81 Point maxtrimul(Point s,int k)//用递归定义实现快速幂的乘法
82 {
83     Point ans;//用来存放结果的
84     ans.init();
85     if(k==1)return s;
86     ans=maxtrimul(s,k>>1);//每次二分
87     ans=mul(ans,ans);
88     if(k&1) //奇数时再乘一次
89     {
90         ans=mul(s,ans);
91     }
92     return ans;
93
94 }
95
96 Point maxtrisum(Point s,int k)
97 {
98     if(k==1)return s;
99        Point ans;//用来保存答案
100     ans.init();
101     ans=add(ans,maxtrimul(s,k>>1));
102     ans=mul(ans,maxtrisum(s,k>>1));
103     if(k&1)//奇数时
104     {
105         ans=add(ans,maxtrimul(s,k));
106     }
107     return ans;
108
109 }
110
111 int main()
112 {
113     cin>>n>>k>>m;
114     Point s;
115     for(int i=1;i<=n;++i)
116     {
117         for(int j=1;j<=n;++j)
118         {
119             cin>>s.a[i][j];
120         }
121     }
122     s=maxtrisum(s,k);
123     display(s);
124
125 }
126

四也 2011-11-27 10:58 发表评论

POJ 1828

四也 — Thu, 24 Nov 2011 03:39:00 GMT

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 }

四也 2011-11-24 11:39 发表评论

POJ 1723

四也 — Tue, 22 Nov 2011 13:24:00 GMT

我真是太菜了。。。看了N个别人的解答，就是不懂。。直到这个出现，我终于懂了一点。。。。

首先考虑纵坐标：

对纵坐标做一次排序，那么，只要最终选择的纵坐标不小于最小的，且不大于最大的，那么对于一头一尾两个点，效果都是相同的；依此类推，所以，选择的纵坐标就是整个纵坐标序列的中位数了，简单吧？

再来考虑横坐标：

还是进行一次升序排列，很显然，这就是最终的顺序了（否则肯定会浪费移动次数），即：

X1 -> X0

X2 -> X0 + 1

...

Xn -> X0 + n - 1

也就是：

X1 -> X0

X2 - 1 -> X0

...

Xn - (n - 1) -> X0 //

来自http://blog.sina.com.cn/s/blog_67ac571c0100itfv.html
下面是我自己的的代码了TVT~

1 #include<iostream>
2 #include<algorithm>
3 #include<cmath>
4 using namespace std;
5 //========================================
6 int x[10010];
7 int y[10010];
8 int main()
9 {
10     int n;
11     cin>>n;
12     int counts=0;
13     for(int i=0;i<n;++i)
14     {
15         cin>>x[i]>>y[i];
16     }
17     sort(y,y+n);
18     sort(x,x+n);
19     int yz=y[n/2];
20     for(int i=0;i<n;++i)
21     {
22         x[i]=x[i]-i;
23     }
24     sort(x,x+n);
25     int xz=x[n/2];
26     for(int i=0;i<n;++i)
27     {
28         counts+=(abs(y[i]-yz)+abs(x[i]-xz));
29     }
30     cout<<counts<<endl;
31
32
33
34 }

四也 2011-11-22 21:24 发表评论

C++博客-Sai

还是POJ3984__BFS【四种记录路径的方法总结】

POJ 3984 方法一【BFS+Stack 记录路径】

【算法导论】动态规划实现

POJ 1050 二维最大子矩阵

POJ 2479 最大子段和 问题

POJ 1458 最长公共子列

POJ 3070 这个为矩阵相乘的基础题。

POJ 3233 快速幂和二分。。。基本上是别人的代码，自己改动一些，不过收获很大。

POJ 1828

POJ 1723

POJ 2479 最大子段和问题