shunfurh
编程介的小学生
2017-10-31 01:51

The Shortest Path

  • path
  • c
  • x
  • matrix
  • lines

Problem Description
There are N cities in the country. Each city is represent by a matrix size of M*M. If city A, B and C satisfy that A*B = C, we say that there is a road from A to C with distance 1 (but that does not means there is a road from C to A).
Now the king of the country wants to ask me some problems, in the format:
Is there is a road from city X to Y?
I have to answer the questions quickly, can you help me?

Input
Each test case contains a single integer N, M, indicating the number of cities in the country and the size of each city. The next following N blocks each block stands for a matrix size of M*M. Then a integer K means the number of questions the king will ask, the following K lines each contains two integers X, Y(1-based).The input is terminated by a set starting with N = M = 0. All integers are in the range [0, 80].

Output
For each test case, you should output one line for each question the king asked, if there is a road from city X to Y? Output the shortest distance from X to Y. If not, output "Sorry".

Sample Input
3 2
1 1
2 2
1 1
1 1
2 2
4 4
1
1 3
3 2
1 1
2 2
1 1
1 1
2 2
4 3
1
1 3
0 0

Sample Output
1
Sorry

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答

为你推荐

换一换