题意 :给你r*c的一块稻田,每个点都种有水稻,青蛙们晚上会从水稻地里穿过并踩倒,确保青蛙的每次跳跃的长度相同,且路线是直线,给出n个青蛙的脚印点问存在大于等于3的最大青蛙走的连续的脚印个数。
思路 : 暴力了一下,顺便剪剪枝就可以过。。。。
//POJ1054
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm> using namespace std ; struct node{
int row,col ;
}plant[];
int ab[][] ;
int r,c,n ; bool cmp(const node a,const node b)
{
if(a.row == b.row)
return a.col < b.col ;
return a.row < b.row ;
}
bool judge(int x,int y)
{
if(x > && x <= r && y > && y <= c) return true ;
return false ;
} int xxxx(int x,int y,int dx,int dy)
{
int cnt = ;
while(judge(x,y))
{
if(!ab[x][y]) return ;//会出现交叉路径所得
cnt ++ ;
x += dx ;
y += dy ;
}
return cnt ;
} int main()
{
scanf("%d %d %d",&r,&c,&n) ;
memset(ab,,sizeof(ab)) ;
for(int i = ; i < n ; i++)
{
scanf("%d %d",&plant[i].row,&plant[i].col) ;
ab[plant[i].row][plant[i].col] = ;
}
sort(plant,plant+n,cmp) ;
int cnt = ;
for(int i = ; i < n ; i++)
{
for(int j = i+ ; j < n ; j++)
{
int dx = plant[j].row-plant[i].row ;
int dy = plant[j].col-plant[i].col ;
if(plant[i].row + cnt *dx > r || cnt*dy + plant[i].col>c) continue ;//青蛙的起点肯定在稻田外;
if(judge(plant[i].row-dx,plant[i].col-dy)) continue ;//该点的直线上的脚印一定要大于上一次的点数;
if(!judge(plant[i].row + cnt*dx,plant[i].col+cnt * dy)) continue ;//多于上一点的基础上点要在稻田内;
cnt = max(cnt,xxxx(plant[i].row,plant[i].col,dx,dy)) ;
}
}
if(cnt < )
printf("0\n") ;
else printf("%d\n",cnt) ;
return ;
}