python

5.8 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

`POJ` `1300` `Door Man`

一、题目描述

你是一座大庄园的管家。庄园有很多房间，编号为0、1、2、3，…。你的主人是一个心不在焉的人，经常沿着走廊随意地把房间的门打开。多年来，你掌握了一个诀窍：沿着一个通道，穿过这些大房间，并把房门关上。你的问题是能否找到一条路径经过所有开着门的房间，并使得：

1 通过门后立即把门关上
2 关上了的门不再打开
3 最后回到你自己的房间（房间0），并且所有的门都已经关闭了。

在本题中，给定房间列表，及连通房间的、开着的门，并给定一个起始房间，判断是否存在这样的一条路径。不需要输出这样的路径，只需判断是否存在。假定任意两个房间之间都是连通的（可能需要经过其他房间）。

输入描述：输入文件包含多个（最多可达100个）测试数据，每个测试数据之间没有空行隔开。每个测试数据包括3 部分：起始行－格式为START M N，其中 M 为管理员起始所处的房间号，N 为房间的总数（1≤N≤20）；房间列表－一共N 行，每行列出了一个房间通向其他房间的房间号（只需列出比它的号码大的房间号，可能有多个，按升序排列），比如房间3 有门通向房间1、5、7，则房间3 的信息行内容为5 7，第一行代表房间0，最后一行代表行间N-1。有可能有些行为空行，当然最后一行肯定是空行，因为N-1 是最大的房间号；两个房间之间可能有多扇门连通。终止行－内容为END。输入文件最后一行是ENDOFINPUT，表示输入结束。

输出描述：每个测试数据对应一行输出，如果能找到一条路关闭所有的门，并且回到房间0，则输出YES X，X 是他关闭的门的总数，否则输出NO。

二、前置知识

`Q`:如何处理带空格的字符串输入？

#include <iostream>
#include <sstream> //istringstream 必须包含这个头文件
#include <string>
using namespace std;
int main() {
    string source = "i an a boy";

    // 声明一个字符串输入流
    istringstream sin;
    // 将字符串导入到sin输入流中
    sin.str(source);

    // 分离的方法1
    string s;
    while (sin >> s) {
        cout << s << endl;
    }
    cout << "===============================" << endl;

    // 重复使用必须先清空
    sin.clear();
    // 重新加载，准备二次输入，或者sin的重用
    sin.str(source);
    string a, b, c, d;
    sin >> a >> b >> c >> d;
    cout << a << endl;
    cout << b << endl;
    cout << c << endl;
    cout << d << endl;
    return 0;
}

二、解题思路

以房间为顶点、连接房间之间的门为边构造图。根据题目的意思，输入文件中每个测试数据所构造的图都是连通的。本题实际上是判断一个图中是否存在欧拉回路或欧拉通路，要分两种情况考虑：

1 如果所有的房间都有偶数个门（通往其他房间），那么有欧拉回路，可以从0 号房间出发，回到0 号房间。但是这种情况下，出发的房间必须为0，因为要求回到0 号房间。例如，第1 个测试数据所对应的图为图5.6(a)，图中有浅色阴影的顶点（即顶点0），表示管家初始时所处的房间；在该测试数据中，管家可以回到0号房间。

有两个房间的门数为奇数，其余的都是偶数，如果出发的房间和0号房间的门数都是奇数，那么也可以从出发的房间到达0号房间，并且满足题目要求。但是不能从房间0出发，必须从另一个门数为奇数的房间出发。例如第2、3 个测试数据就是这种情形，对应的图为图(b)和图(c)，输出的结果分别是NO和YES 7。对于庄园的其他情形，都是不能完成题目中所要求的任务的，所以直接输出NO。

本题的难点在于输入数据的处理：可以使用sscanf函数处理数据。

#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <cstring>
using namespace std;

const int N = 20;
int m, n, d[N];

int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ1300.in", "r", stdin);
#endif
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    string s;
    while (getline(cin, s), s != "ENDOFINPUT") {
        memset(d, 0, sizeof d); // 多组测试数据，清空度数组

        istringstream sin;
        sin.str(s);         // 用s输入进行构建
        sin >> s >> m >> n; // 进1出3

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            getline(cin, s);         // 读取整行
            if (!s.size()) continue; // 如果本行输入是空的，那么处理下一行
            sin.clear();             // istringstream这东西如果想重复使用，需要先清空
            sin.str(s);              // 用s输入进行构建
            int j;
            while (sin >> j) { // 循环输出j
                d[i]++, d[j]++;
                ++cnt;
            }
        }
        // 读入END
        getline(cin, s);

        // 检查欧拉回路和欧拉路径
        int odd = 0;
        for (int i = 0; i < n; i++)
            if (d[i] % 2) odd++;

        if (odd == 0 && m == 0)
            cout << "YES " << cnt << endl;
        else if (odd == 2 && m != 0)
            cout << "YES " << cnt << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

5.8 KiB Raw Permalink Blame History Unescape Escape

POJ 1300 Door Man