首页 > 代码库 > POJ - 1054 The Troublesome Frog
POJ - 1054 The Troublesome Frog
题意:给你个矩阵,里面有n个标记的点,许多只青蛙在上面跳,每次跳的距离都是一样的且轨迹是直线,目标是从一边跳到另一边,求最多步数的青蛙
思路:排序后,枚举判断
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 5050; struct point{ int x,y; void init(int X, int Y) { x = X; y = Y; } }a[MAXN]; int map[MAXN][MAXN]; int r,c,n; int cmp(point A, point B) { if (A.x == B.x) return A.y < B.y; return A.x < B.x; } int in(int x, int y) { if (x < 1 || y < 1 || x > r || y > c) return 0; return 1; } int main() { int x,y; scanf("%d%d", &r ,&c); scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%d", &a[i].x, &a[i].y); map[a[i].x][a[i].y] = 1; } sort(a, a+n, cmp); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { int nx = a[j].x - a[i].x; int ny = a[j].y - a[i].y; if (in(a[i].x-nx, a[i].y-ny) || !in(a[j].x+ans*nx, a[j].y+ans*ny) || !map[a[j].x+ans*nx][a[j].y+ans*ny]) continue; int cnt = 0; int x = a[j].x + nx; int y = a[j].y + ny; int flag = 1; while (in(x, y)) { if (!map[x][y]){ flag = 0; break; } else cnt++; x += nx; y += ny; } if (flag) ans = cnt; } } printf("%d\n", ans>0?ans+2:0); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。