当前位置：首页 → 问答吧 → the troublesome frog

the troublesome frog

时间：2011-08-05

来源：互联网

关于这道题目有几个不明白的地方，一个是青蛙可以从几条边跳入，二是跳出的边是不是正好和跳入的边相对。

作者: zouleixhyz 发布时间: 2011-08-05

貌似做过，那出来晒晒
C/C++ code


#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 5001;
struct Plant {
int x, y;
bool operator < (const Plant &p)
const {
if(x != p.x) return x < p.x;
return y < p.y;
}
}plant[MAXN];

int n, row, col;
void solve()
{
Plant first, second, step, cur;
int i, j, k, ans_max = 0;
for(i = 0; i < n; i++)
for(j = i + 1; j < n; j++) {
step.x = plant[j].x – plant[i].x;
step.y = plant[j].y – plant[i].y;
first = plant[i]; //线路的第一个点
second = plant[j]; //线路的第二个点
if((first.x – step.x) > 0 && (first.y – step.y)> 0 && (first.y – step.y) <= col)continue; //必须从外面跳入
if(first.x + ans_max * step.x > row || first.y + ans_max * step.y <= 0 || first.y + ans_max * tep.y > col)continue; //取当前方案无法得到比当前最优解更大，故不取此方案
int pre = j, temp = 2;
cur.x = second.x + step.x;
cur.y = second.y + step.y;
while(cur.x <= row && cur.x > 0 && cur.y > 0 && cur.y <= col)
{
for(k = pre + 1; k < n; k++)
if(plant[k].x == cur.x && plant[k].y == cur.y) break;
if(k == n) { temp = 2; break ; }
temp ++;
cur.x += step.x;
cur.y += step.y;
pre = k;
}

if(temp >= 3 && temp > ans_max) ans_max = temp;
}

cout << ans_max << endl;
}

int main()
{
cin >> row >> col >> n; 
for(int i = 0; i < n; i++)
cin >> plant[i].x >> plant[i].y;
sort(plant, plant + n);
solve();
return(0);
}