首页 > 专题系列 > Java解POJ > POJ 3626 Mud Puddles [解题报告] Java
2013
11-12

POJ 3626 Mud Puddles [解题报告] Java

Mud Puddles

问题描述 :

Farmer John is leaving his house promptly at 6 AM for his daily milking of Bessie. However, the previous evening saw a heavy rain, and the fields are quite muddy. FJ starts at the point (0, 0) in the coordinate plane and heads toward Bessie who is located at (X, Y) (-500 ≤ X ≤ 500; -500 ≤ Y ≤ 500). He can see all N (1 ≤ N ≤ 10,000) puddles of mud, located at points (Ai, Bi) (-500 ≤ Ai ≤ 500; -500 ≤ Bi ≤ 500) on the field. Each puddle occupies only the point it is on.

Having just bought new boots, Farmer John absolutely does not want to dirty them by stepping in a puddle, but he also wants to get to Bessie as quickly as possible. He’s already late because he had to count all the puddles. If Farmer John can only travel parallel to the axes and turn at points with integer coordinates, what is the shortest distance he must travel to reach Bessie and keep his boots clean? There will always be a path without mud that Farmer John can take to reach Bessie.

输入:

* Line 1: Three space-separate integers: X, Y, and N.
* Lines 2..N+1: Line i+1 contains two space-separated integers: Ai and Bi

输出:

* Line 1: The minimum distance that Farmer John has to travel to reach Bessie without stepping in mud.

样例输入:

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

样例输出:

11

解题代码:

//* @author:

import java.io.BufferedInputStream;
import java.util.LinkedList;
import java.util.Scanner;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
public class Main {

    static int[][] field = new int[1001][1001];
    static int y;
    static int n;
    static int x;

    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        x = scan.nextInt();
        y = scan.nextInt();
        n = scan.nextInt();
        field[x + 500][y + 500] = 1;
        for (int i = 0; i < n; i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            field[a + 500][b + 500] = -1;
        }
        solve();
    }

    public static void solve() {
        System.out.println(bsf(500, 500));
    }
    public static int bsf(int r, int c) {

        LinkedList< Point> queue = new LinkedList();
        queue.add(new Point(r, c, 0));
        field[r][c] = -1;

        while (!queue.isEmpty()) {
            Point current = queue.removeFirst();
            int ai = current.a;
            int bi = current.b;

            if (ai - 1 >= 0 && field[ai - 1][bi] == 0) {
                queue.addLast(new Point(ai - 1, bi, current.step + 1));
                field[ai - 1][bi] = -1;
            } else if (field[ai - 1][bi] == 1) {
                return current.step + 1;
            }

            if (ai + 1 <= 1000 && field[ai + 1][bi] == 0) {
                queue.addLast(new Point(ai + 1, bi, current.step + 1));
                field[ai + 1][bi] = -1;
            } else if (field[ai + 1][bi] == 1) {
                return current.step + 1;
            }
            if (bi - 1 >= 0 && field[ai][bi - 1] == 0) {
                queue.addLast(new Point(ai, bi - 1, current.step + 1));
                field[ai][bi - 1] = -1;
            } else if (field[ai][bi - 1] == 1) {
                return current.step + 1;
            }

            if (bi + 1 <= 1000 && field[ai][bi + 1] == 0) {
                queue.addLast(new Point(ai, bi + 1, current.step + 1));
                field[ai][bi + 1] = -1;
            } else if (field[ai][bi + 1] == 1) {
                return current.step + 1;
            }
        }
        return 0;
    }
}

class Point {

    int a = 0;
    int b = 0;
    int step = 0;

    public Point(int a, int b, int step) {
        this.a = a;
        this.b = b;
        this.step = step;
    }
}

  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  3. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  4. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?