从昨晚上起来, 连续的login, 终于到了今天凌晨4点左右摆脱了time out的阴影.
进去摸了好久, 才找以偶的NO.14 room, 于是就开始答题, 对着please choose one的下拉菜单选了一个题来做, 完了后才发现那下拉菜单里的两个都要做, 做到最后时, 一直习惯cisco做题时间到都会自动submit,于是等着时候到时,点submit, 居然时间过了不让提交, 甚是郁闷...
还第一次看到这样的比赛上可以写C#的, 不过想想C#写出来的效率貌似不占优势.
这里面的题还是偏基础, 只考了第二道题, 以下是第二道题目,和偶的一个末submit的类
Problem Statement
????
You are given a string[] grid representing a rectangular grid of letters. You are also given a string find, a word you are to find within the grid. The starting point may be anywhere in the grid. The path may move up, down, left, right, or diagonally from one letter to the next, and may use letters in the grid more than once, but you may not stay on the same cell twice in a row (see example 6 for clarification).
You are to return an int indicating the number of ways find can be found within the grid. If the result is more than 1,000,000,000, return -1.
Definition
????
Class:
WordPath
Method:
countPaths
Parameters:
string[], string
Returns:
int
Method signature:
int countPaths(string[] grid, string find)
(be sure your method is public)
????
Constraints
-
grid will contain between 1 and 50 elements, inclusive.
-
Each element of grid will contain between 1 and 50 uppercase ('A'-'Z') letters, inclusive.
-
Each element of grid will contain the same number of characters.
-
find will contain between 1 and 50 uppercase ('A'-'Z') letters, inclusive.
Examples
0)
????
{"ABC",
"FED",
"GHI"}
"ABCDEFGHI"
Returns: 1
There is only one way to trace this path. Each letter is used exactly once.
1)
????
{"ABC",
"FED",
"GAI"}
"ABCDEA"
Returns: 2
Once we get to the 'E', we can choose one of two directions for the final 'A'.
2)
????
{"ABC",
"DEF",
"GHI"}
"ABCD"
Returns: 0
We can trace a path for "ABC", but there's no way to complete a path to the letter 'D'.
3)
????
{"AA",
"AA"}
"AAAA"
Returns: 108
We can start from any of the four locations. From each location, we can then move in any of the three possible directions for our second letter, and again for the third and fourth letter. 4 * 3 * 3 * 3 = 108.
4)
????
{"ABABA",
"BABAB",
"ABABA",
"BABAB",
"ABABA"}
"ABABABBA"
Returns: 56448
There are a lot of ways to trace this path.
5)
????
{"AAAAA",
"AAAAA",
"AAAAA",
"AAAAA",
"AAAAA"}
"AAAAAAAAAAA"
Returns: -1
There are well over 1,000,000,000 paths that can be traced.
6)
????
{"AB",
"CD"}
"AA"
Returns: 0
Since we can't stay on the same cell, we can't trace the path at all.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
My answer:
public class WordPath
{
int pathCount = 0;
public int countPaths( string[] grid, string find )
{
//get the first grid
for( int i = 0; i < grid.Length; i ++ )
{
for( int j = 0; j < grid[i].Length; j ++ )
if ( grid[i].Substring( j, 1 ) == find.Substring( 0, 1 ) )
searchNext( grid, i, j, find.Substring( 1 ) );
}
int temp = pathCount;
pathCount = 0;
if( temp > 1000000000 )
return -1;
else
return temp;
}
private void searchNext( string[] grid, int currentX, int currentY, string find )
{
if( find == string.Empty )
{
if( pathCount > 1000000000 )
return;
pathCount ++;
return;
}
for( int i = currentX - 1; i <= currentX + 1; i ++ )
{
if( i < 0 )
continue;
if( i >= grid.Length )
continue;
for( int j = currentY - 1; j <= currentY + 1; j ++ )
{
if( j < 0 )
continue;
if( j >= grid[i].Length )
continue;
if( i == currentX && j == currentY )
continue;
try
{
if( grid[i].Substring( j, 1 ) == find.Substring( 0, 1 ) )
searchNext( grid, i, j, find.Substring( 1 ) );
}
catch{}
}
}
}
}