3

我是 Python 新手，我正在尝试解决 Kingdom Connectivity 的 interviewstreet 问题。虽然，我设法解决了这个问题，但我在输入给定格式时遇到了麻烦，我已经在我的系统上尝试了我的解决方案并且输出是正确的，但是一旦我在那里编译，就没有输出。

输入的形式为：

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

请帮我弄清楚如何解决这个问题。

目前，我从raw_input()循环中获取输入并使用a.split(' ').

这是问题的一部分：

**Input Description:**

First line contains two integers N and M.

Then follow M lines ,each having two integers say x and y, 1<=x,y<=N , indicating there is a road from city x to city y.

**Output Description:**

Print the number of different paths from city 1 to city N modulo 1,000,000,000(10^9).If there are infinitely many different paths print "INFINITE PATHS"(quotes are for clarity).

**Sample Input:**

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

**Sample Output:**

2

**Sample Input:**

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

**Sample Output:**

INFINITE PATHS

这是我的解决方案

import sys
import numpy as np
c=0
x=raw_input()
y=x.split(' ')
l=(int(y[0]),int(y[1]))
e=[raw_input() for i in range(l[1])]
f=[e[i].split(' ') for i in range(l[1])]
a=[map(int,i) for i in f]
b=[[0 for i in a] for j in range(l[0])]
for i in range(l[0]+1):
    for j in range(l[0]+1):
        if [i,j] in a:
            b[i-1][j-1]=1
        elif a[i-1][0]>=a[i-1][1]:
            print "INFINITE PATHS"
            sys.exit(0)
for i in range(0,l[1]): 
    d=np.linalg.matrix_power(b,i+1)
    c+=d[0][l[1]-1]   
print c

这是截图 在此处输入图像描述

4

3 回答 3

3

我发现你的程序很难理解。所以，我重写了它，我认为我的版本更容易理解。

import sys
import numpy as np


line = raw_input()
max_val, num_paths = (int(n) for n in line.split())


# a will be a list of tuples of int, taken from the input.
#
# Each tuple represents a path, so this is effectively a sparse representation
# of a square matrix of possible paths.
#
# Input city numbers are 1-based, but we will treat them as 0-based, so
# subtract 1 from each value before appending to array a.

a = []
for _ in xrange(num_paths):
    line = raw_input()

    # TRICKY: subtract 1 to convert from 1-based to 0-based city numbers
    tup = tuple(int(n)-1 for n in line.split())

    if len(tup) != 2:
        raise ValueError, "input should only have two values per line"
    for n in tup:
        if not 0 <= n < max_val:
            raise ValueError, "value must be in range [1, %d]" % max_val
        if tup[0] >= tup[1]:
            #raise ValueError, "INFINITE PATHS"
            print "INFINITE PATHS"
            sys.exit(0)
    a.append(tup)


# Expand the sparse matrix representation into an actual square matrix.
# It should have a 1 anywhere a path was indicated with a tuple in list a,
# and a 0 everywhere else.
b = [ [0 for _ in xrange(max_val)] for _ in xrange(max_val)]
for i, j in a:
    b[i][j] = 1


c = 0
for i in xrange(num_paths):
    d = np.linalg.matrix_power(b, i + 1)
    c += d[0][max_val - 1]
print c

2给定示例输入时，我的版本会打印。

以下是我在处理此问题时发现的一些事情：

第一行给了我们常量（在文档中N，M分别代表最大合法值和路径数）。您应该将这些值保存在具有良好名称的变量中，而不是将它们放在列表中并通过列表索引引用它们。我使用了名称max_val和num_paths. 你自己犯了一个错误：你应该找到从城市 1 到城市 N 的路径，所以最后的检查应该是d[0][max_val - 1]; 你用l[1]which isnum_paths而不是l[0].

b应该是方阵。您的代码根据 的长度设置宽度，a但可能并不总是相等，所以这是一种危险的方法。max_valnum_paths

循环遍历方阵中的每个可能点并检查它是否应该设置为 1 是很奇怪的。它也非常低效，特别是因为in测试是 O(n) 其中 n 是数组的长度a。相反，构建空方阵，然后简单地循环路径并为每个路径设置 1 个值。

同样，在初始化方阵的循环中验证输入值也很奇怪。最好在输入循环中读取输入值时对其进行验证。而且这很危险，因为num_paths可能与max_val. 这也是低效的，因为您在;a[i-1][0]中a[i-1][1]的每列检查一次 b该比较根本不使用该值j。你每次检查五次；每次检查一次就足够了。

我使用了一个 Python 成语，_当您不关心变量的值时，可以使用（单个下划线）作为变量的名称。当我们只是用循环做某事一定次数，并且我们不会将循环计数器值用于任何事情时，我使用 a_作为循环计数器变量。这当然不是必需的。

回答您的实际问题：我认为您的程序没有任何可能的方式不产生输出。我怀疑运行此测试问题的服务器上可能存在问题。您的程序应始终打印“INFINITE PATHS”或某种整数值。

PS我实际上并不了解您的程序是如何工作的；问题描述说你应该提供一些以 1e9 为模的路径，我看不出有什么可以强制执行的。

于 2012-03-20T00:25:20.860 回答
1

您可以按如下方式读取指定的输入：

line = raw_input()
n, m = map(int, line.split())

for _ in range(m):
  line = raw_input()
  x, y = map(int, line.split())
  print x, y
于 2012-03-19T22:12:06.317 回答
0

如果您在与脚本位于同一文件夹中的文件 input.txt 中有输入：

with open("input.txt") as f:
    l = [int(i) for i in f.readline().split(" ")]
    a = []
    for line in f.readlines():
        a.append([int(i) for i in line.strip().split(" ")])
print(l, a)

如果输入作为命令行参数传递：

import sys
input_string = sys.argv[1]
print(input_string) # test if this prints the input
...
于 2012-03-19T22:34:06.297 回答