Google 2015 校园招聘(APAC)的一道机试题目

Problem

Vincenzo decides to make cube IV but only has the budget to make a square maze. Its a perfect maze, every room is in the form of a square and there are 4 doors (1 on each side of the room). There is a big number written in the room. A person can only move from one room to another if the number in the next room is larger than the number in his current room by 1. Now, Vincenzo assigns unique numbers to all the rooms (1, 2, 3, …. \(s^{2}\)) and then places \(s^{2}\) people in the maze, 1 in each room where S is the side length of the maze. The person who can move maximum number of times will win. Figure out who will emerge as the winner and the number of rooms he will be able to move.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of S which is the side length of the square maze. Then \(s^{2}\) numbers follow like a maze to give the numbers that have been assigned to the rooms.

1
2
3
1 2 9
5 3 8
4 6 7

Output

For each test case, output one line containing “Case #x: r d”, where x is the test case number (starting from 1), r is the room number of the person who will win and d is the number of rooms he could move. In case there are multiple such people, the person who is in the smallest room will win.

Limits
1 ≤ T ≤ 100.

Small dataset
1 ≤ S ≤ 10

Large dataset
1 ≤ S ≤\(10^{3}\)

Sample:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input
2
2
3 4
1 2
3
1 2 9
5 3 8
4 6 7
Output
Case #1: 1 2
Case #2: 6 4


  题目公布在Google Code jam上。
  题目大致的意思就是在一个\(S\times S\) 的迷宫里\(S^{2}\)个小格子),每个小格子就是一个房间,用数字从1到\(S^{2}\)给这\(S^{2}\)个房间随机编号,每个房间的编号唯一。每个房间的4面墙上都有一扇门(在迷宫边缘的门是打不开的),转移到下一个房间的规则是下一个房间的编号必须比当前房间的编号大1。现在每个房间都有一个人,谁访问房间数最多的则获胜。如果有多人出发点能够有最多访问房间数,则出发时所在房间(起点)编号最小的获胜。要求输出获胜者出发时的房间编号以及访问房间次数。

解题思路

  用一个同样大小的矩阵(暂且叫地图矩阵)记录每个房间所能转移的信息。0表示无法继续转移,1,2,3,4分别表示可以向上,右,下,左转移。
  比如迷宫A

1
2
3
1 2 9
5 3 8
4 6 7

  相对应的地图矩阵B是

1
2
3
2 3 0
3 0 1
1 2 1

  接下来就在地图矩阵上遍历每个位置(房间)以及计算从该位置出发所能访问到的房间数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
伪代码
i,j ;//表示位置的行,列坐标
roomNumber; //记录解的出发时所在的房间编号
counter = 1; // 搜索访问房间数,第一个访问到的房间是出发时所在的房间
for each B(i,j)://遍历每一个房间
counter_temp=1;//记录当前这个出发点能访问到的房间数
itemp =i;jtemp=j ;
while( B(itemp,jtemp) !=0 )
{
[itemp,jtemp] = move(itemp,jtemp)
counter_temp++;
}
if ( counter_temp >= counter )
{
if ( counter_temp > counter ) //找到更忧的出发点
{
counter = counter_temp;
roomNumber = A(i,j);
}
else if( counter_temp == counter ) //如果访问房间数相同,取出发点的编号最小
{
if( A(i,j) < roomNumber )
{
roomNumber = A(i,j);
}
}
}
end
得到解 roomNumber , counter ;

  c\c++代码在这里下载,可自行到google jam 上测试。要注意的是代码中实现地图矩阵是用一维数组模拟的,也就是用一维数组模拟二维数组。