首页 > 专题系列 > Java解POJ > POJ 1137 The New Villa [解题报告] Java
2013
11-09

POJ 1137 The New Villa [解题报告] Java

The New Villa

问题描述 :

Mr. Black recently bought a villa in the countryside. Only one thing bothers him: although there are light switches in most rooms, the lights they control are often in other rooms than the switches themselves. While his estate agent saw this as a feature, Mr. Black has come to believe that the electricians were a bit absent-minded (to put it mildly) when they connected the switches to the outlets.

One night, Mr. Black came home late. While standing in the hallway, he noted that the lights in all other rooms were switched off. Unfortunately, Mr. Black was afraid of the dark, so he never dared to enter a room that had its lights out and would never switch off the lights of the room he was in.

After some thought, Mr. Black was able to use the incorrectly wired light switches to his advantage. He managed to get to his bedroom and to switch off all lights except for the one in the bedroom.

You are to write a program that, given a description of a villa, determines how to get from the hallway to the bedroom if only the hallway light is initially switched on. You may never enter a dark room, and after the last move, all lights except for the one in the bedroom must be switched off. If there are several paths to the bedroom, you have to find the one which uses the smallest number of steps, where “move from one room to another”, “switch on a light” and “switch off a light” each count as one step.

输入:

The input file contains several villa descriptions. Each villa starts with a line containing three integers r, d, and s. r is the number of rooms in the villa, which will be at most 10. d is the number of doors/connections between the rooms and s is the number of light switches in the villa. The rooms are numbered from 1 to r; room number 1 is the hallway, room number r is the bedroom.

This line is followed by d lines containing two integers i and j each, specifying that room i is connected to room j by a door. Then follow s lines containing two integers k and l each, indicating that there is a light switch in room k that controls the light in room l.

A blank line separates the villa description from the next one. The input file ends with a villa having r = d = s = 0, which should not be processed.

输出:

For each villa, first output the number of the test case (‘Villa #1′, ‘Villa #2′, etc.) in a line of its own.

If there is a solution to Mr. Black’s problem, output the shortest possible sequence of steps that leads him to his bedroom and only leaves the bedroom light switched on. (Output only one shortest sequence if you find more than one.) Adhere to the output format shown in the sample below.

If there is no solution, output a line containing the statement `The problem cannot be solved.’

Output a blank line after each test case.

样例输入:

3 3 4
1 2
1 3
3 2
1 2
1 3
2 1
3 2

2 1 2
2 1
1 1
1 2

0 0 0

样例输出:

Villa #1
The problem can be solved in 6 steps:
- Switch on light in room 2.
- Switch on light in room 3.
- Move to room 2.
- Switch off light in room 1.
- Move to room 3.
- Switch off light in room 2.

Villa #2
The problem cannot be solved.

解题代码:

//* @author:alpc12
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.lang.Integer;

class Node {
    int x, mask;

    int s;

    int f;

    int action;

    public Node(int x, int mask, int s, int f, int aa) {
        this.x = x;
        this.mask = mask;
        this.s = s;
        this.f = f;
        this.action = aa;
    }
}

public class Main {

    int r, d, s;

    boolean[][] adj;

    boolean[][] ctr;

    int[][] dp;

    void run() throws Exception {
        Scanner cin = new Scanner(System.in);
        int tc = 0;
        while (true) {

            r = cin.nextInt();
            d = cin.nextInt();
            s = cin.nextInt();

            if (r == 0 && d == 0 && s == 0)
                break;
            System.out.printf("Villa #%d\n", ++tc);

            int i;
            adj = new boolean[r][r];
            ctr = new boolean[r][r];
            dp = new int[r][1 << r];

            for (i = 0; i < r; ++i) {
                Arrays.fill(dp[i], -1);
            }

            for (i = 0; i < d; ++i) {
                int x = cin.nextInt();
                int y = cin.nextInt();
                adj[x - 1][y - 1] = adj[y - 1][x - 1] = true;
            }

            for (i = 0; i < s; ++i) {
                int x = cin.nextInt();
                int y = cin.nextInt();
                ctr[x - 1][y - 1] = true;
            }

            List< Node> Q = new ArrayList< Node>();

            Q.add(new Node(0, 1, 0, -1, 0));
            Node now = new Node(0, 1, 0, -1, 0);
            dp[0][1] = 0;
            int lo = 0;
            while (lo < Q.size()) {
                now = Q.get(lo);
                int x = now.x, mask = now.mask, s = now.s;
                if (x == r - 1 && mask == (1 << (r - 1))) {
                    break;
                }

                for (i = 0; i < r; ++i)
                    if (adj[x][i] && (mask & (1 << i)) != 0) {
                        if (dp[i][mask] == -1) {
                            dp[i][mask] = s + 1;
                            Q.add(new Node(i, mask, s + 1, lo, 0));
                        }
                    }

                for (i = 0; i < r; ++i)
                    if (ctr[x][i]) {
                        if ((mask & (1 << i)) != 0 && i != x) {
                            if (dp[x][mask ^ (1 << i)] == -1) {
                                dp[x][mask ^ (1 << i)] = s + 1;
                                Q.add(new Node(x, mask ^ (1 << i), s + 1, lo, -i - 1));
                            }
                        } else {
                            if (dp[x][mask | (1 << i)] == -1) {
                                dp[x][mask | (1 << i)] = s + 1;
                                Q.add(new Node(x, mask | (1 << i), s + 1, lo, i + 1));
                            }
                        }
                    }
                lo++;
            }

            if (lo == Q.size()) {
                System.out.printf("The problem cannot be solved.\n");
            } else {
                System.out.printf("The problem can be solved in %d steps:\n", now.s);
                ArrayList idxes = new ArrayList();
                while (lo != -1) {
                    // System.out.println(lo);
                    idxes.add(lo);
                    lo = Q.get(lo).f;
                }
                for (i = idxes.size() - 2; i >= 0; --i) {
                    if (Q.get(idxes.get(i)).action == 0) {
                        System.out.printf("- Move to room %d.\n", Q.get(idxes.get(i)).x + 1);
                    } else if (Q.get(idxes.get(i)).action > 0) {
                        System.out.printf("- Switch on light in room %d.\n", Q.get(idxes.get(i)).action);
                    } else {
                        System.out.printf("- Switch off light in room %d.\n", -Q.get(idxes.get(i)).action);
                    }
                }
            }
            System.out.println();

        }
    }

    public static void main(String[] args) throws Exception {
        new Main().run();

    }

    private String toBinary(int x) {
        String now = Integer.toBinaryString(x);
        for (int i = 0; i < r - now.length(); ++i) {
            now = "0" + now;
        }
        return now;
    }

}

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  3. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!