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

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

2024-07-07 22:11:19   226人阅读

题目链接

看到分类里是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 }

 


联系
我们