poj1054 讨厌的青蛙

Posted on | In |

题意：在一个row*col的矩阵里，留了n个青蛙的脚印。已知每只青蛙的步长是一定的，且都是从一个边界外，跳到了另一边的边界外，而且跳的是直线。每跳落地就留一个脚印在那个格子。现在问你那只在地里留下最多脚印的青蛙留下了多少只脚印(只要有可能就好)。
image

思路

  1. 首先针对 x 从小到大排序，然后枚举，这样为后面的剪枝提供了方便;
    2.对于剪枝，因为题目中明确说了：青蛙是从外面跳进来，至少踩了 3 个黑点，然后跳出去的，于是可以加下面剪枝：

    a. 确定 2 点之间的间距之后，确定出发点之前的那个点是否在稻田外面，如果不是则剪枝;

    b. 根据当前最优情况，确定当前的点只要要走多少步才能找到一个更优解，相当于是一个启发式的剪枝;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<bitset>
#include<algorithm>
using namespace std;
int R,C,n;
struct PLANT{
	int x;
	int y; 
}plants[5000];
bool operator <(PLANT t1,PLANT t2){
	if(t1.x==t2.x) return t1.y<t2.y;
	else return t1.x<t2.x;
}
int search_path(PLANT plant,int dx,int dy){
	PLANT t;
	t.x=plant.x+dx;
	t.y=plant.y+dy;
	int steps=2;
	while(1<=t.x&&t.x<=R&&t.y>=1&&t.y<=C){
		if(!binary_search(plants,plants+n,t)){
        ////每一步都必须踩倒水稻才算合理, 否则这就不是一条行走路径
			steps=0;
			break;
		}
		t.x+=dx;
		t.y+=dy;//!!
		steps++;
	}
	return steps;
}
int main(){
	int R1,C1;
	scanf("%d%d",&R,&C);
	scanf("%d",&n);
	for(int i=0;i<n;i++){
	scanf("%d%d",&R1,&C1);
		plants[i].x=R1;
		plants[i].y=C1;
		
	}
	sort(plants,plants+n);//!! 二分查找必须先排序
	int max=2;
	for(int i=0;i<n-2;i++){//!!
		for(int j=i+1;j<n-1;j++){
			int dx=plants[j].x-plants[i].x;
			int dy=plants[j].y-plants[i].y;
			int px=plants[i].x-dx;
			int py=plants[i].y-dy;//!!
	if(px>=1&&px<=R&&py>=1&&py<=C) continue; 
    ///第一点的前一点在稻田里,
//说明本次选的第二点导致的x方向步长不合理(太小)
// 取下一个点作为第二点

   	if(plants[i].x+(max-1)*dx>R) break;
    ////x方向过早越界了. 说明本次选的第二点不成立
//如果换下一个点作为第二点, x方向步长只会更大, 更不成立, 所以应该
//认为本次选的第一点必然是不成立的, 那么取下一个点作为第一点再试
		if(plants[i].y+(max-1)*dy<1||plants[i].y+(max-1)*dy>C) break;
        // //y方向过早越界了, 应换一个点作为第二点再试
			int steps=search_path(plants[j],dx,dy);
			if(steps>max) max=steps;
			
		}
		
	}
	if(max==2) max=0;
	cout<<max<<endl;
	return 0;
}