矩阵数字的一个路径的算法,怎么利用C语言编写程序的方式实现的

Problem Description
Problems that process input and generate a simple yes'' orno'' answer are called decision problems. One class of decision problems, the NP-complete problems, are not amenable to general efficient solutions. Other problems may be simple as decision problems, but enumerating all possible ``yes'' answers may be very difficult (or at least time-consuming).

This problem involves determining the number of routes available to an emergency vehicle operating in a city of one-way streets.

Given the intersections connected by one-way streets in a city, you are to write a program that determines the number of different routes between each intersection. A route is a sequence of one-way streets connecting two intersections.

Intersections are identified by non-negative integers. A one-way street is specified by a pair of intersections. For example, j k indicates that there is a one-way street from intersection j to intersection k. Note that two-way streets can be modeled by specifying two one-way streets: j k and k j .

Consider a city of four intersections connected by the following one-way streets:

0 1
0 2
1 2
2 3

There is one route from intersection 0 to 1, two routes from 0 to 2 (the routes are 0-1-2 and 0-2 ), two routes from 0 to 3, one route from 1 to 2, one route from 1 to 3, one route from 2 to 3, and no other routes.
It is possible for an infinite number of different routes to exist. For example if the intersections above are augmented by the street , there is still only one route from 0 to 1, but there are infinitely many different routes from 0 to 2. This is because the street from 2 to 3 and back to 2 can be repeated yielding a different sequence of streets and hence a different route. Thus the route 0-2-3-2-3-2 is a different route than 0-2-3-2 .

Input
The input is a sequence of city specifications. Each specification begins with the number of one-way streets in the city followed by that many one-way streets given as pairs of intersections. Each pair j k represents a one-way street from intersection j to intersection k. In all cities, intersections are numbered sequentially from 0 to the ``largest'' intersection. All integers in the input are separated by whitespace. The input is terminated by end-of-file.

There will never be a one-way street from an intersection to itself. No city will have more than 30 intersections.

Output
For each city specification, a square matrix of the number of different routes from intersection j to intersection k is printed. If the matrix is denoted M, then M[j][k] is the number of different routes from intersection j to intersection k. The matrix M should be printed in row-major order, one row per line. Each matrix should be preceded by the string ``matrix for city k'' (with k appropriately instantiated, beginning with 0).

If there are an infinite number of different paths between two intersections a -1 should be printed. DO NOT worry about justifying and aligning the output of each matrix. All entries in a row should be separated by whitespace.

Sample Input
7 0 1 0 2 0 4 2 4 2 3 3 1 4 3
5
0 2
0 1 1 5 2 5 2 1
9
0 1 0 2 0 3
0 4 1 4 2 1
2 0
3 0
3 1

Sample Output
matrix for city 0
0 4 1 3 2
0 0 0 0 0
0 2 0 2 1
0 1 0 0 0
0 1 0 1 0
matrix for city 1
0 2 1 0 0 3
0 0 0 0 0 1
0 1 0 0 0 2
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
matrix for city 2
-1 -1 -1 -1 -1
0 0 0 0 1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
0 0 0 0 0

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

1
一个C语言方面有关分数矩阵的问题
1
用C 语言编程,实现矩阵(3行3列)的转置(即行列互换)
1
输入一个3行4列的整数矩阵,计算并输出对角线上的元素之和
1
M*N算法矩阵,是否是使用二位数组,怎么利用C语言实现
1
如何用C语言实现求给定矩阵的逆矩阵?
1
多个矩阵相乘程序的编写,我是新手,急,大家帮帮忙
1
C语言的函数算法去解决一个矩阵的问题,涉及到大数的计算怎么实现的?
0
GM的矩阵的算法,GM的大小由输入给定,具体怎么实现,用C语言
0
一个有关安于邻接矩阵的问题,是如何利用C语言编程实现的呢
0
查找最近的车站的一个算法问题,采用邻接矩阵的方式的表述,怎么计算的,运用C语言的相关知识
0
数字矩阵里数字的移动的问题,输出移动行的数字,采用C语言如何实现?
0
三角形矩阵的求和的算法,如何利用C语言的办法计算三角形和
0
采用C语言的办法计算矩阵的共约数的问题的解决
1
矩阵里元素交换的一个算法,如何利用C语言的编程的技术实现的办法
0
运用C语言是如何解决这里的矩阵的一个转换颠倒的算法的?具体的思路
0
矩阵 的Hadamard积的数据结构的算法,采用C语言编程技术如何实现的思路
0
关于在矩阵中进行的路径的查找的算法,如何使用C语言来编程实现
0
求矩阵的点积的算法问题,分为多行,怎么用C语言的方式实现的
0
NxN矩阵棋盘着色问题的符号处理,采用C语言算法编程的实现方式