题意 :给你r*c的一块稻田,每个点都种有水稻,青蛙们晚上会从水稻地里穿过并踩倒,确保青蛙的每次跳跃的长度相同,且路线是直线,给出n个青蛙的脚印点问存在大于等于3的最大青蛙走的连续的脚印个数。
思路 : 暴力了一下,顺便剪剪枝就可以过。。。。
1 //POJ1054 2 #include <stdio.h> 3 #include <string.h> 4 #include <iostream> 5 #include <algorithm> 6 7 using namespace std ; 8 9 struct node{ 10 int row,col ; 11 }plant[5010]; 12 int ab[5010][5010] ; 13 int r,c,n ; 14 15 bool cmp(const node a,const node b) 16 { 17 if(a.row == b.row) 18 return a.col < b.col ; 19 return a.row < b.row ; 20 } 21 bool judge(int x,int y) 22 { 23 if(x > 0 && x <= r && y > 0 && y <= c) return true ; 24 return false ; 25 } 26 27 int xxxx(int x,int y,int dx,int dy) 28 { 29 int cnt = 0 ; 30 while(judge(x,y)) 31 { 32 if(!ab[x][y]) return 0 ;//会出现交叉路径所得 33 cnt ++ ; 34 x += dx ; 35 y += dy ; 36 } 37 return cnt ; 38 } 39 40 int main() 41 { 42 scanf("%d %d %d",&r,&c,&n) ; 43 memset(ab,0,sizeof(ab)) ; 44 for(int i = 0 ; i < n ; i++) 45 { 46 scanf("%d %d",&plant[i].row,&plant[i].col) ; 47 ab[plant[i].row][plant[i].col] = 1 ; 48 } 49 sort(plant,plant+n,cmp) ; 50 int cnt = 2 ; 51 for(int i = 0 ; i < n ; i++) 52 { 53 for(int j = i+1 ; j < n ; j++) 54 { 55 int dx = plant[j].row-plant[i].row ; 56 int dy = plant[j].col-plant[i].col ; 57 if(plant[i].row + cnt *dx > r || cnt*dy + plant[i].col>c) continue ;//青蛙的起点肯定在稻田外; 58 if(judge(plant[i].row-dx,plant[i].col-dy)) continue ;//该点的直线上的脚印一定要大于上一次的点数; 59 if(!judge(plant[i].row + cnt*dx,plant[i].col+cnt * dy)) continue ;//多于上一点的基础上点要在稻田内; 60 cnt = max(cnt,xxxx(plant[i].row,plant[i].col,dx,dy)) ; 61 } 62 } 63 if(cnt < 3) 64 printf("0\n") ; 65 else printf("%d\n",cnt) ; 66 return 0 ; 67 }
POJ 1054 The Troublesome Frog(枚举+剪枝),布布扣,bubuko.com
POJ 1054 The Troublesome Frog(枚举+剪枝)
原文:http://www.cnblogs.com/luyingfeng/p/3789467.html