首页 > 专题系列 > Java解POJ > POJ 1806 Manhattan 2025 [解题报告] Java
2013
11-10

POJ 1806 Manhattan 2025 [解题报告] Java

Manhattan 2025

问题描述 :

Background

Manhattan in the year 2025 – it is so densely populated that its old two-dimensional grid of streets and avenues fails to provide enough space for all the traditional vehicles such as cars, bicycles, or busses.Accordingly, the newly developed 3D-Skyjetters become very popular, because they allow to pass the traffic jams on the ground by flying in the air. After a series of horrible accidents caused by 3D-Skyjetters cutting a corner, New York authorities have put into place new regulations of air traffic and are determined to enforce them rigorously. The key point of these regulations is that 3D-Skyjetters must follow virtual airways on a three-dimensional rectangular grid, easy enough for the New Yorkers who had to use the two-dimensional rectangular grid of roads on the ground all their life.

Problem

You own a company that rents out 3D-Skyjetters. As 3D-Skyjetters are in such an early state of development,they are far from being economical. So your customers keep running out of petrol at all the wrong places,and you need a system to inform them about their current range at all times.

You may assume that travelling from one intersection to the next in the grid takes one unit of petrol, no matter if the customer is moving horizontally or vertically, up or down. You may also assume that your customer is located at some intersection where his or her movements are not restricted by the ground or other obstacles, but just by the amount of remaining petrol.

Given the amount of petrol, provide a graphical representation of all the intersections in the range of your customer, along with the amount of petrol that is needed to go there.

输入:

The first line of the input contains the number of scenarios. For each scenario, there is a line containing the units of remaining petrol, i.e an integer u satisfying 0 <= u <= 9. If more than 9 units of petrol remain, the customer will ignore the display anyway.

输出:

Start the output for each scenario with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a graphical (or rather textual) representation of all intersections that can be reached with the given amount of petrol, along with the units of petrol necessary to go there. In this graphical representation, print the slices of the smallest axis-aligned three-dimensional cube containing all the intersections in the range, and label the slices from the bottom to the top starting at 1. For each slice,start the output with a line containing “slice #s:”, where s is the number of the slice. In the lines that follow, print a graphical representation of all the intersections in that slice, using
  • the digits 0 to 9 for intersections in the range, representing the amount of petrol necessary to go there,
  • and the dot “.” for intersections not in the range.

Print an additional blank line after each scenario.

样例输入:

2
0
2

样例输出:

Scenario #1:
slice #1:
0

Scenario #2:
slice #1:
.....
.....
..2..
.....
.....
slice #2:
.....
..2..
.212.
..2..
.....
slice #3:
..2..
.212.
21012
.212.
..2..
slice #4:
.....
..2..
.212.
..2..
.....
slice #5:
.....
.....
..2..
.....
.....

解题代码:

//* @author: 
import java.util.*;

public class Main {

    static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            System.out.println("Scenario #" + (i + 1) + ":");
            solve();
            System.out.println();
        }
    }

    public static void solve() {
        int originRow, originCol, n;
        n = originRow = originCol = in.nextInt();
        char[][][] point = new char[n + 1][n + 1][2 * n + 1];
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                for (int k = 0; k < 2 * n + 1; k++) {
                    point[i][j][k] = '.';
                }
            }
        }

        for (int i = 0; i < n + 1; i++) {
            for (int j = originRow - i; j <= originRow; j++) {
                int num = 0;
                for (int k = originCol - i + originRow - j; k <= originCol; k++) {
                    point[i][j][k] = (char) (n - num + '0');
                    num++;
                }
                num = 0;
                for (int k = originCol + i - originRow + j; k > originCol; k--) {
                    point[i][j][k] = (char) (n - num + '0');
                    num++;
                }
            }
        }
        print(point);
    }

    public static void print(char[][][] point) {
        int n = 0;
        for (int i = 0; i < point.length; i++) {
            n++;
            System.out.println("slice #" + n + ":");
            for (int j = 0; j < point[i].length; j++) {
                for (int k = 0; k < point[i][j].length; k++) {
                    System.out.print(point[i][j][k]);
                }
                System.out.println();
            }
            for (int j = point[i].length - 2; j >= 0; j--) {
                for (int k = 0; k < point[i][j].length; k++) {
                    System.out.print(point[i][j][k]);
                }
                System.out.println();
            }
        }
        for (int i = point.length - 2; i >= 0; i--) {
            n++;
            System.out.println("slice #" + n + ":");
            for (int j = 0; j < point[i].length; j++) {
                for (int k = 0; k < point[i][j].length; k++) {
                    System.out.print(point[i][j][k]);
                }
                System.out.println();
            }
            for (int j = point[i].length - 2; j >= 0; j--) {
                for (int k = 0; k < point[i][j].length; k++) {
                    System.out.print(point[i][j][k]);
                }
                System.out.println();
            }
        }
    }
}

  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  3. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测