首页 > 代码库 > poj 1054 The Troublesome Frog (暴力搜索 + 剪枝优化)

poj 1054 The Troublesome Frog (暴力搜索 + 剪枝优化)

题目链接

看到分类里是dp,结果想了半天,也没想出来,搜了一下题解,全是暴力!

不过剪枝很重要,下面我的代码 266ms。

题意:

在一个矩阵方格里面,青蛙在里面跳,但是青蛙每一步都是等长的跳,

从一个边界外,跳到了另一边的边界外,每跳一次对那个点进行标记。

现在给你很多青蛙跳过后的所标记的所有点,那请你从这些点里面找出

一条可能的路径里面出现过的标记点最多。

分析:先排序(目的是方便剪枝,break),然后枚举两个点,这两个

点代表这条路径的起始的两个点。然后是三个剪枝,下面有。

开始遍历时,预判当前能否产生比ans更好地解,若不能,直接跳到下一个。。。。

注意标记点必须>=3,否则输出0.

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define Max(a,b)((a)>(b)?(a):(b))
 6 using namespace std;
 7 const int maxn = 5000 + 10;
 8 bool f[maxn][maxn];
 9 int n, r, c, cx, cy;
10 struct node
11 {
12     int x, y;
13 }p[maxn];
14 
15 bool cmp(node a, node b)
16 {
17     if(a.y == b.y)
18     return a.x < b.x;
19     else
20     return a.y < b.y;
21 }
22 bool check(int x, int y)
23 {
24     if(x>=1&&x<=r && y>=1&&y<=c)
25     return true;
26     return false;
27 }
28 int cal(int px, int py)
29 {
30     int sum = 1;
31     while(1)
32     {
33         if(!check(px+cx, py+cy))
34         break;
35         if(f[px+cx][py+cy])
36         {
37             sum++;
38             px += cx; py += cy;
39         }
40         else
41             return 0;
42     }
43     return sum;
44 }
45 int main()
46 {
47     int i, j, ans;
48     while(~scanf("%d%d", &r, &c))
49     {
50         memset(f, 0, sizeof(f));
51         scanf("%d", &n);
52         for(i = 0; i < n; i++)
53             {
54                 scanf("%d%d", &p[i].x, &p[i].y);
55                 f[p[i].x][p[i].y] = true;
56             }
57         sort(p, p+n, cmp);
58 
59         ans = 2;
60         for(i = 0; i < n; i++)
61         for(j = i+1; j < n; j++)
62         {
63            cx = p[j].x - p[i].x; cy = p[j].y - p[i].y;
64            if(check(p[i].x-cx, p[i].y-cy)) //判断是不是从稻田之外跳过来的
65            continue;
66            if(p[i].y+ans*cy>c) //因为y是递增的,如果最大的ans 在稻田之外,后面也都大于
67            break;
68            if(!check(p[i].x+ans*cx, p[i].y+ans*cy))
69            continue;  //这个不要写成break,因为x不是递增的,有可能前一个出界,但是后一个不出界。
70            ans = Max(ans, cal(p[i].x, p[i].y));
71         }
72         if(ans < 3)
73         printf("0\n");
74         else
75         printf("%d\n", ans);
76     }
77     return 0;
78 }