`
isiqi
  • 浏览: 16554860 次
  • 性别: Icon_minigender_1
  • 来自: 济南
社区版块
存档分类
最新评论

Google中国编程挑战赛-题目解答

阅读更多

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.












Java的解答

public class WordPath
{
public int countPaths(String[] grid, String find)
{
mx = grid.length;
my = grid[0].length();
charRect = new char[grid.length][];
for(int i=0;i<charRect.length;i++)
charRect[i] = grid[i].toCharArray();
finds = find.toCharArray();

int count = 0;
char first = finds[0];
for(int x=0;x<charRect.length;x++)
for(int y=0;y<charRect[x].length;y++)
if (charRect[x][y] == first)
count += countPaths(0,x,y);

if (count > 1000000000)
return -1;
return count;
}

char[][] charRect = null;
char[] finds = null;
int mx = 0;
int my = 0;

private int countPaths(int ind,int cx,int cy)
{
if (ind == finds.length - 1)
return 1;

int count = 0;
char nextChar = finds[ind+1];

for(int dx=-1;dx<=1;dx++)
{
for(int dy=-1;dy<=1;dy++)
{
if (dx==0 && dy == 0)
continue;

int x = cx + dx;
int y = cy + dy;
if (x >=0 && x< mx && y >= 0 && y < my)
{
if (charRect[x][y] == nextChar)
count += countPaths(ind+1,x,y);
}
}
}

return count;
}
分享到:
评论

相关推荐

    2023-python编程挑战赛(所有组别).pdf

    ### 2023 Python编程挑战赛知识点解析 #### 一、比赛背景与目标 - **比赛名称**:“2023 Python编程挑战赛”面向全国青少年电子信息智能创新大赛。 - **比赛对象**:分为小学组和中学组,旨在通过实践编程激发青...

    Google中国编程大赛入围赛真题

    在Google中国编程大赛中,参赛者们通常会面临一系列挑战性的题目,旨在考察他们的编程技能、算法理解以及问题解决能力。本次入围赛的真题包含了两个文档:Google750.doc和Google-250.doc,很可能是两道不同难度级别...

    高含金量国际计算机编程竞赛.pdf

    7. Google Code Jam:谷歌全球编程挑战赛,是一个全球性的编程竞赛,旨在提高学生的编程能力和算法设计能力。 8. Facebook Hacker Cup:Facebook黑客杯,是一个全球性的编程竞赛,旨在提高学生的编程能力和算法设计...

    Google编程大赛题目

    在Google编程大赛中,参赛者通常会面临一系列挑战性的题目,旨在测试他们的编程技能、算法理解和问题解决能力。这些题目通常涉及计算机科学的基础知识,包括数据结构、算法、数学、逻辑推理以及特定领域的应用,例如...

    有哪些含金量比较高的编程比赛? (2).docx

    - 赛事通常包含一系列挑战性的算法题目,考验参赛者的逻辑思维能力和编程技能。 #### 参赛方式 - 比赛分为线上预选赛和线下决赛两个阶段。 - 预选赛通过解决算法问题的方式进行筛选;决赛则邀请顶尖选手到Facebook...

    google算法编程大赛.zip

    【描述】:在"google算法编程大赛.zip"这个压缩包中,包含了一系列与编程竞赛相关的题目和资源,这些题目反映了实际比赛可能遇到的问题类型。参赛者需要运用他们的编程技巧和算法理解来解决这些问题,例如文件名所示...

    google-foobar:Google Foo Bar挑战赛的解决方案

    在IT领域,Google Foo Bar挑战赛是一场广为人知的编程竞赛,旨在寻找技术精湛的开发者。这个比赛通常涉及到一系列的算法和逻辑难题,而"google-foobar"这个压缩包很可能是参赛者或参与者分享的解决方案集合。在这个...

    挑战编程英文版(全)en-all

    该书作为计算机科学领域的重要参考资料,由Springer出版社出版,涵盖了广泛的编程挑战题目和解题策略,适用于那些渴望在程序设计竞赛中取得优异成绩的学习者。 ### 重要知识点 #### 1. 编程竞赛概述 编程竞赛是一...

    第一届“中国软件杯”大学生软件设计大赛题目副本.pdf

    【聚焦搜索引擎与网络爬虫】 在信息技术日新月异的时代,搜索引擎已经成为我们获取信息不可或...这样的挑战既锻炼了学生的编程能力,又培养了他们解决实际问题的思维,对于推动中国软件行业的创新和发展具有重要意义。

    Google竞赛题(c语言)

    在Google的竞赛中,C语言经常被用作...同时,不断练习和参与实际的编程挑战,能帮助你提升解决问题的能力和速度。在准备过程中,可以尝试解决过去的竞赛题目,了解题目的风格和常见陷阱,这将对你的比赛表现大有裨益。

    有哪些含金量比较高的编程比赛?.docx

    在IT行业中,编程竞赛不仅是对参与者技能的一种挑战与提升,也是衡量个人或团队技术实力的重要标准之一。参加高质量的编程比赛不仅可以帮助开发者提高解决问题的能力、拓宽思路,还能够增加求职时的竞争力,甚至有...

    google算法编程大赛.rar

    这个赛事旨在检验参赛者的算法设计、问题解决以及编程技能,通过一系列富有挑战性的题目,激发参赛者在计算机科学领域的创新思维和实践能力。大赛的历届真题无疑是宝贵的资源,可以帮助我们了解谷歌对于优秀程序员的...

    天梯赛信息、介绍、要求天梯赛,是一种编程竞赛,旨在通过解决一系列编程问题来锻炼参赛者的算法设计能力、编程实现能力和团队协

    1. **Google Code Jam**:作为全球知名的编程竞赛之一,Google Code Jam每年吸引成千上万的编程高手参与。该竞赛聚焦于算法和数据结构的挑战,不仅提升了参赛者的技能水平,还为其职业生涯增添了亮点。 2. **ACM-...

    挑战编程程序设计竞赛训练手册

    《挑战编程程序设计竞赛训练手册》就是这类专业指导书籍的代表,它不仅涵盖了基础算法和数据结构,还深入讲解了问题解决策略和编程技巧,并提供了丰富的实战练习和历年竞赛题目。 编程竞赛中的算法部分是考察参赛者...

    谷歌杯2011 上海复旦邀请赛problems

    该赛事由谷歌公司赞助,旨在通过解决一系列具有挑战性的算法问题来检验参赛者的编程能力和逻辑思维能力。此次比赛不仅吸引了来自复旦大学的学生,还有其他高校的学生参与其中。 #### 二、题目解析 ##### 1A. ...

    google-kick-start-2021-python:我的Google Kick Start 2021解决方案:person_running:

    【Google Kick Start 2021】是谷歌举办的一系列在线编程竞赛,旨在挑战和激励全球的编程爱好者提升他们的算法和编码技能。参赛者需要在限定时间内解决一系列精心设计的问题,这些问题通常涉及到数据结构、算法和逻辑...

    141007比赛出题.zip

    【标题】"141007比赛出题.zip"是一个压缩包文件,根据其命名推测,这可能是某个编程竞赛或编程挑战的题目集合。在IT行业中,这样的比赛通常用于测试和提升参赛者的编程技能、算法理解以及问题解决能力。这类比赛的...

    Google_code_jam.rar_Google jam_google code jam_google code jam j

    Google Code Jam是谷歌举办的一项全球性的编程竞赛,旨在挑战参赛者的算法设计和问题解决能力。这个压缩包"Google_code_jam.rar"包含了某位参赛者对Google Code Jam比赛中的问题的解决方案。从标签"google_jam"、...

Global site tag (gtag.js) - Google Analytics