Google编程大赛入围赛750分真题 第五组
思路:
广度搜索。
数据结构: 两个vector,一个保存当前的位置 current,一个保存下一步的位置 next
算法:
1. 在矩阵里找字符串的第一个字母,然后放到current里
2. 逐个搜寻current里的字符的邻居,看是不是字符串里的第二个字符,是就放到next里面
3. 判断next的长度是不是超过1000000
4. 将next赋给current,将next清空
5. 重复第一步
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.
我的思路如下,不过运行未能返回正确结果,仅供参考:
using System;
using System.Collections;
public class WordPath
{
public int countPaths(string[] grid, string find)
{
int m = 0;
int h = grid.Length;
for(int i = 0; i < h ; i ++)
{
for(int j = 0; j < grid[i].Length ; j ++)
{
if(grid[i][j] == find[0])
{
// all
m += GetNext(grid,find,i,j,1,m);
}
}
}
return m;
}
private int GetNext(string[] grid,string find , int m ,int n ,int f,int t)
{
int x = grid.Length;
int[,] im = {{0,1},{0,-1},{1,0},{-1,0},{-1,1},{1,-1},{-1,-1},{1,1}};
for(int i = 0; i < 8; i++)
{
int p = im[i,0]+m;
int q = im[i,1]+n;
if(p>-1 && q>-1 && p<x && q<x && grid[p][q] == find[f])
{
if(f+1 == find.Length)
{
t += 1;
}
else
GetNext(grid,find,p,q,f+1,t);
}
}
return t;
}
}
public class WordPath {
private String find="";
private static int count=0;
public WordPath() {
}
public int countPaths(String[] grid, String find){
this.find=find;
char[][] cs=new char[grid.length][grid[0].length()];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j <grid[i] .length(); j++) {
cs[i][j]=grid[i].charAt(j);
}
}
for (int i = 0; i < cs.length; i++) {
for (int j = 0; j <cs[i] .length; j++) {
if(cs[i][j]==find.charAt(0))
{
go(cs,0,i,j);
}
}
}
if(count>1000000000)
count=-1;
return count;
}
public void go(char[][] cs,int index,int x,int y)
{
if(index==find.length()-1)
{
count++;
return ;
}
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if(i==0&&j==0)
continue;
if(x+i<0||x+i>cs.length-1)
continue ;
if(y+j<0||y+j>cs[0].length-1)
continue ;
if(cs[x+i][y+j]==find.charAt(index+1))
go(cs,index+1,x+i,y+j);
}
}
}
public static void main(String[] args) {
WordPath wordPath1 = new WordPath();
}
}
namespace S3{
const unsigned int MAX_COUNT = 1000000000;
const unsigned int MAX_UINT = 0xFFFFFFFF;
struct cell
{
char ch;
int count[2];
};
class CGrid
{
typedef cell* LPCELL;
public:
CGrid() : m_RowCount(0), m_ColCount(0), m_ppCells(NULL) { }
~CGrid() { Clear(); }
bool Initialize(const std::vector<std::string>& grid)
{
Clear();
m_RowCount = grid.size();
if (m_RowCount <= 0)
{
return false;
}
m_ColCount = grid[0].size();
if (m_ColCount <= 0)
{
return false;
}
for (int i=0; i<m_RowCount; i++)
{
if (grid[i].size() != m_ColCount)
{
return false;
}
}
int nCount = m_RowCount * m_ColCount;
m_ppCells = new LPCELL[nCount];
if (m_ppCells == NULL)
{
return false;
}
for (i=0; i<m_RowCount; i++)
{
for (int j=0; j<m_ColCount; j++)
{
LPCELL p = new cell;
m_ppCells[i * m_ColCount + j] = p;
p->ch = grid[i][j];
}
}
return true;
}
int CountPath(const std::string& find)
{
int nLen = find.size();
if (nLen <= 0)
{
return 0;
}
con
#---------------in python-----------------------
### example 0
### Returns: 1
##grid = ['ABC', 'FED', 'GHI']
##find = 'ABCDEFGHI'
### example 1
### Returns: 2
##grid = ['ABC', 'FED', 'GAI']
##find = 'ABCDEA'
### example 2
### Returns: 0
##grid = ['ABC', 'DEF', 'GHI']
##find = 'ABCD'
### example 3
### Returns: 108
##grid = ['AA', 'AA']
##find = 'AAAA'
### example 4
### Returns: 56448
##grid = ['ABABA', 'BABAB', 'ABABA', 'BABAB', 'ABABA']
##find = 'ABABABBA'
### example 5
### Returns: -1
grid = ['AAAAA', 'AAAAA', 'AAAAA', 'AAAAA', 'AAAAA']
find = 'AAAAAAAAAAA'
### example 6
### Returns: 0
##grid = ['AB', 'CD']
##find = 'AA'
class WordPath:
def __init__(self):
pass
def countPaths(self, grid, find):
#prepare the searchResult matrix
self.searchResult = []
for i in range(len(grid)):
self.searchResult.append([])
for i in range(len(grid)):
for j in range(len(grid[0])):
self.searchResult[i].append({})
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
result = self.search(grid, i, j, find)
if result == -1:
return -1
count = count + result
感觉这是最好的答案:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <time.h>
using namespace std;
const int neigh[8][2] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
const int Max = 1000000000;
class WordPath
{
private:
int result ;
int map[3][52][52];
int X,Y;
bool level;
public:
inline int fresult()
{
int i,j;
result = 0;
for (i=1; i <= X; i++)
for (j=1; j <= Y; j++)
{
result += map[level][i][j];
if (result > Max) return -1;
}
return result;
}
int countPaths(vector <string> grid, string findpath)
{
int i,j,k,l,m,n,q;
X = grid[0].size();
Y = X;
memset(map,0,sizeof map);
level = 0;
for (i=1; i <= X; i++)
for (j=1; j <= Y; j++)
{
map[2][i][j] = grid[i-1][j-1];
if (map[2][i][j] == findpath[0])
map[level][i][j] = 1;
};
if (findpath.length()==1)
return fresult();
for (k=1; k < findpath.length(); k++)
{
level = !level;
for (i=1; i <= X; i++)
for (j=1; j <= Y; j++)
if (map[2][i][j] == findpath[k])
for (l=0; l < 8; l++)
{
map[level][i][j] += map[!level][i+neigh[l][0]][j+neigh[l][1]];
if (ma
算法可以,远比想的简单。
//--------------------------------------
import java.util.*;
import java.text.*;
class Data {
private static char[][] rectangle = {
{'A', 'B','A','B', 'A'},
{'B', 'A','B','A', 'B'},
{'A', 'B','A','B', 'A'},
{'B', 'A','B','A', 'B'},
{'A', 'B','A','B', 'A'},
};
private static String stf = "ABABABBA";
public static String stringToFind() {
return stf;
}
public static char[][] rectangleToSearch() {
return rectangle;
}
public int MAXIMUM = 100000;
}
class Position {
private int x, y;
private static int recWidth, recHeight;
private static Data d;
public static void Init(Data d_) {
d = d_;
recWidth = d.rectangleToSearch().length;
recHeight = d.rectangleToSearch()[0].length;
}
public Position(int x, int y) {
this.x = x;
this.y = y;
}
public int X() {
return x;
}
public int Y() {
return y;
}
public char charValue() {
return d.rectangleToSearch()[x][y];
}
public ArrayList neighbor() {
ArrayList result = new ArrayList();
int nx, ny;
for ( int i = -1; i != 2
分享到:
相关推荐
Google中国编程大赛入围赛真题
个人作品,参加本校的程序设计大赛入围决赛,无缘大奖,现在发给大家,权当是个反面教材吧,呵呵
广联达2009算量大赛入围人员软件应用技巧分享.doc
包含第六、七、八、九、十、十一、十二等历届蓝桥杯完整真题。附赠选拔赛,省赛试题及python教程和蓝桥杯相关考点的集训教程。 蓝桥杯全国软件和信息技术专业人才大赛简称“蓝桥杯”,是由工业和信息化部人才交流...
中国创新创业大赛互联网行业总决赛入围企业.docx中国创新创业大赛互联网行业总决赛入围企业.docx
中美创客大赛总决赛入围项目-脉象未来-APP版
中国创新创业大赛先进制造行业总决赛入围企.docx中国创新创业大赛先进制造行业总决赛入围企.docx
物联网大赛相关程序代码、设计文档、使用说明,供参考 物联网大赛相关程序代码、设计文档、使用说明,供参考 物联网大赛相关程序代码、设计文档、使用说明,供参考 物联网大赛相关程序代码、设计文档、使用说明,供...
大赛内容共分:(1)软件应用与开发,(2)微课与教学辅助,(3)数字媒体(简称数媒)设计普通组,(4)数媒设计专业组,(5)数媒设计1911年前中华优秀传统文化元素,(6)数媒设计中华民族服饰手工艺品建筑,(7...
计算机设计大赛内容说明及要求(1) 附件一:计算机设计大赛内容说明及要求 一、大赛作品内容分类 1.插画设计类: 说明: (1)每队参赛人数为1-3人,指导教师不多于2人。 (2)插画设计的要求如下: 作品风格鼓励...
中国科学技术大学少年班 创新班 科创考试数学物理2015-2020历年真题,适用初三,高一,高二考少年班或创新班的真题解析
备注:插画设计类除了正常参与校赛评审外,还将由公司参与评奖并设单独奖金,一等奖1名1000元,二等奖一名500元,三等奖一名300元,另有入围奖若干名,均有奖品赠送。 2.软件应用与开发类 包括以下小类: (1)Web...
形式检查:大赛竞赛委员会赛务组对报名表格、材料、作品等进行形式检查。针对有缺陷的作品提示参赛队在规定时间内修正。对报名分类不恰当的作品纠正其分类。 2.作品分组:对所有在规定时间内提交的有效参赛作品分组...
第四届国际青少年音乐节暨国际青少年器乐大赛网络赛区决选入围名单.pdf
Hulu本周结束竞购报价 雅虎Google亚马逊入围.docx
1.关于IPC中国PCB设计大赛 2.赛题设计总体要求 3.本届PCB设计大赛考核重点 4.入围选手作品概况 5.电路模块设计要点解析 6.DDR4电路模块的仿真分析
公益创意项目入围项目doc-分类.doc
数计学院第八届综合技能大赛系列活动之—— 网页设计大赛 为提高我院同学计算机应用技能特别是网络技术的能力,完善我院同学从事任教的 技能,以增强班级凝聚力并丰富同学们的课余文化生活,我院特举办第八届综合...
择善网,个金所产品比赛(入围奖)