一道 Google 竞赛题的解法
2007-03-15 21:53:07 来源:WEB开发网 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚悢鍏尖拻閻庨潧澹婂Σ顔剧磼閻愵剙鍔ょ紓宥咃躬瀵鎮㈤崗灏栨嫽闁诲酣娼ф竟濠偽i鍓х<闁绘劦鍓欓崝銈囩磽瀹ュ拑韬€殿喖顭烽幃銏ゅ礂鐏忔牗瀚介梺璇查叄濞佳勭珶婵犲伣锝夘敊閸撗咃紲闂佽鍨庨崘锝嗗瘱闂備胶顢婂▍鏇㈠箲閸ヮ剙鐏抽柡鍐ㄧ墕缁€鍐┿亜韫囧海顦﹀ù婊堢畺閺屻劌鈹戦崱娆忓毈缂備降鍔庣划顖炲Φ閸曨垰绠抽悗锝庝簽娴犻箖姊洪棃娑欐悙閻庢矮鍗抽悰顕€宕堕澶嬫櫖濠殿噯绲剧€笛囧箲閸ヮ剙钃熼柣鏂挎憸閻熷綊鏌涢…鎴濇灈妞ゎ剙鐗嗛—鍐Χ鎼粹€茬凹缂備緡鍠楅幐鎼佹偩閻戣棄纭€闁绘劕绉靛Λ鍐春閳ь剚銇勯幒鎴濐伀鐎规挷绀侀埞鎴︽偐閹绘帩浼€缂佹儳褰炵划娆撳蓟濞戞矮娌柟瑙勫姇椤ユ繈姊洪柅鐐茶嫰婢т即鏌熼搹顐e磳闁挎繄鍋涢埞鎴犫偓锝庘偓顓涙櫊閺屽秵娼幏灞藉帯闂佹眹鍊曢幊鎰閹惧瓨濯撮柛鎾村絻閸撳崬顪冮妶鍡楃仸闁荤啿鏅涢悾鐑藉Ψ瑜夐崑鎾绘晲鎼粹剝鐏嶉梺缁樻尰濞叉﹢濡甸崟顖氱疀闂傚牊绋愮花鑲╃磽娴h棄鐓愭慨妯稿妿濡叉劙骞樼拠鑼槰闂佸啿鎼崐濠毸囬弶搴撴斀妞ゆ梻銆嬪銉︺亜椤撶偛妲婚柣锝囧厴楠炴帡骞嬮弮鈧悗濠氭⒑鐟欏嫭鍎楅柛妯衡偓鐔插徍濠电姷鏁告慨鐑藉极閸涘﹥鍙忔い鎾卞灩绾惧鏌熼崜褏甯涢柍閿嬪灦閵囧嫰骞掗崱妞惧缂傚倷绀侀ˇ閬嶅极婵犳氨宓侀柛鈩冪⊕閸婄兘鏌涘┑鍡楊伀妞ゆ梹鍔曢埞鎴︽倻閸モ晝校闂佸憡鎸婚悷锔界┍婵犲洦鍤冮柍鍝勫暟閿涙粓姊鸿ぐ鎺戜喊闁告瑥楠搁埢鎾斥堪閸喓鍘搁柣蹇曞仧绾爼宕戦幘璇茬疀濞达絽鎲¢崐顖炴⒑绾懎浜归悶娑栧劦閸┾偓妞ゆ帒鍟惃娲煛娴e湱澧柍瑙勫灴閹瑩寮堕幋鐘辨闂備礁婀辨灙闁硅姤绮庨崚鎺楀籍閸喎浠虹紓浣割儓椤曟娊鏁冮崒娑氬幈闂佸搫娲㈤崝宀勬倶閻樼粯鐓曢柟鑸妼娴滄儳鈹戦敍鍕杭闁稿﹥鐗犲畷婵嬫晝閳ь剟鈥﹂崸妤€鐒垫い鎺嶈兌缁犲墽鈧厜鍋撳┑鐘辩窔閸嬫鈹戦纭烽練婵炲拑绲垮Σ鎰板箳閹冲磭鍠撻幏鐘绘嚑閼稿灚姣愰梻鍌氬€烽懗鑸电仚濠电偛顕崗妯侯嚕椤愩倖瀚氱€瑰壊鍠栧▓銊︾節閻㈤潧校缁炬澘绉瑰鏌ュ箵閹烘繄鍞甸柣鐘烘鐏忋劌顔忛妷褉鍋撶憴鍕碍婵☆偅绻傞~蹇涙惞閸︻厾锛滃┑鈽嗗灠閹碱偊锝炲鍥╃=濞达綁顥撻崝宥夋煙缁嬪灝鏆遍柣锝囧厴楠炲鏁冮埀顒傜不婵犳碍鍋i柛銉戝啰楠囬悗瑙勬尭缁夋挳鈥旈崘顔嘉ч柛鈩兠棄宥囩磽娴e壊鍎愰柛銊ュ缁顓兼径瀣偓閿嬨亜閹哄秶顦︾€殿喖鐏濋埞鎴﹀煡閸℃浠梺鍛婎焼閸曨収娲告俊銈忕到閸燁垶宕愰崹顐e弿婵☆垳鍘ф禍楣冩倵濮樼偓瀚�

核心提示:本文示例源代码或素材下载 本人于2005年12月13日凌晨参加了google中国编程挑战赛的入围阶段的赛事,虽然最终我感觉自己做出了这道级别为high到mid间的赛题,一道 Google 竞赛题的解法,但是却发现那时入围赛事早已经结束了......相信 vckbase 中的不少朋友肯定也参加了那场入围赛,所以我
本文示例源代码或素材下载
本人于2005年12月13日凌晨参加了google中国编程挑战赛的入围阶段的赛事。虽然最终我感觉自己做出了这道级别为high到mid间的赛题,但是却发现那时入围赛事早已经结束了......
相信 vckbase 中的不少朋友肯定也参加了那场入围赛,所以我打算把自己的解法写出来,一则虽然题目中的测试用例是全部通过了,但这并不能保证我的解法是正确的,希望大家批评指教;二则相信其他朋友也一定有更好的解法大家一起讨论讨论。希望,这篇文章能起到抛砖引玉的效果。
一、竞赛题目
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:
vector < string >, string
Returns:
int
Method signature:
int countPaths(vector < 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.
题目的意思大致是这样的:在类 WordPath 中编写一个原型为:int countPaths(vector < string> grid, string find)
的函数,grid相当于一个字母矩阵,grid中的每个字符串含有相同个数的字母,这些字母都是大写的字母,从''A''到''Z'',grid中字母个数的范围是1-50。参数find是要求你在grid中搜索路径的字符串,其同样只含有''A''到''Z''的字符,其个数范围同样是1-50。搜索起点可以从grid中的任何一点开始,然后可以向上,向下,向左,向右,以及对角线移动一格。grid中的每个位置的字母可以多次使用。但路径不能在相同位置停留两次(见用例6)。返回值是个整型数据,表示搜索到的路径总数数。如果这个数值大于1,000,000,000, 则返回-1。
- ››Google搜索引擎的奥秘
- ››Google测试搜索结果页面右侧内容更丰富的信息栏
- ››Google Dart精粹:应用构建,快照和隔离体
- ››google的代码审查
- ››google analytics清晰追踪爬虫的爬行信息
- ››Google+中文用户在两千万Google+大军中是少数派
- ››Google AdWords最昂贵点击成本的20种关键词分类
- ››Google运作经理Bryan Power给出的GOOGLE求职意见
- ››Google用户体验的十大设计原则
- ››Google Analytics(分析)能为网站带来什么
- ››Google goggles图片搜索 如何优化一个wap网站
- ››Google Docs将增加iPhone和Android编辑功能
赞助商链接