gooleanswer.cpp

n后问题回溯(递归) C/C++编写的n后问题回溯(递归) 欢迎大家使用

// GooleAnswer.cpp : Defines the entry point for the console application.
//
/*
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.
*/
#include <string>
#include <vector>
#include <iostream>
#include <stdio.h>
using namespace std; //Required for TopCoder gcc compiler

//****************************************************************
//类名：WordPath
//作者：roc（[e-mail]）
//日期：2005-12-13
//用途: 本代码为实现上述竞赛题所作。
//注意事项：如欲转载，请保持本段说明。
//****************************************************************
class WordPath
{
    typedef struct POINTtag{
        int x;
        int y;
        int count;
    }POS;
    typedef vector<POS> VETPOS;
    
public:
    
    int countPaths(vector <string> grid, string find)
    {
        int findStrLen = find.length();
        int gridSize   = grid.size();
        int gridStrLen = grid[0].length();
        
        vector <VETPOS> vec(findStrLen);
        
        int i,j,k;
        
        // 遍历grid中的每一个字符
        for ( i = 0; i < gridSize; i ++)
        {
            for ( j= 0; j < gridStrLen; j++)
            {
                for ( k=0; k<findStrLen; k++)
                {
                    char ch =  find.at(k);
                    //如果与find中位置k的字符相等，则将相应的grid中的位置坐标保存到相应的向量中去
                    if ( ch == grid[i].at(j) )
                    {
                        POS ps;
                        ps.x =j;
                        ps.y = i;
                        
                        //位置向量0中所有坐标的初始值为1，而其他位置向量中坐标的这个字段总会被指零后才计算
                        ps.count = 1;
                        vec[k].push_back(ps);
                    }
                }
            }
        }
        
        // 如果有find中的字符在grid中不存在则返回0
        for ( k=0; k<findStrLen; k++)
        {
            if ( vec[k].size() == 0 )
                return 0;
        }
                  
        VETPOS midVes;//保存当前位置向量中符合条件点的临时向量
        
        // 遍历从位置1开始的位置向量
        for ( i = 1; i < findStrLen ; i ++)
        {
            midVes.clear();
            
            //遍历当前位置向量中的所有位置坐标
            for ( j=0; j < vec[i].size(); j++)
            {
                POS cur = vec[i][j];
                
                //如果当前点与前个向量vec[i-1]中的点可以移动到达，则保存这个点到临时变量midVes中去
                if (  pathCount(cur,vec[i-1]))
                {
                    midVes.push_back(cur);
                }
            }
            //清空原来的向量
            vec[i].clear();
            
            //如果midVes中有符合条件的点存在，则将它保存到原来的位置向量中去
            //否则返回0
            if ( midVes.size() >0 )
            {
                vec[i] = midVes;
            }
            else
            {
                return 0;
            }
        }
        
        // 统计保存在最后位置向量中的点的count值
        int count = 0;
        for ( j=0; j < vec[findStrLen-1].size(); j++)
        {
            POS cur = vec[findStrLen-1][j];
            count += cur.count;
            if (count > 1000000000 )
                return -1;
        }
        return count;
    }
    
    int pathCount(POS &ps, VETPOS& pre)
    {
        //初始为0
        ps.count = 0;
        int i;
        
        //遍历pre中的每个位置坐标
        for ( i=0; i < pre.size(); i++)
        {
            //计算cur与pre[i]的纵横坐标差的绝对值
            int xAbs = ps.x - pre[i].x;
            int yAbs = ps.y - pre[i].y;
            
            xAbs = xAbs<0?-xAbs:xAbs;
            yAbs = yAbs<0?-yAbs:yAbs;
           
            //判断是否可以移动到达
            if (( xAbs == 1 && yAbs < 2 ) ||
                ( yAbs == 1 && xAbs < 2 ) )
            {
                ps.count += pre[i].count;//统计通过ps点的可能路径数。
            }
        }
        
        return ps.count;
    }
};


//以下为测试代码
void Load(vector <string> &grid, string &find)
{
    string array[]={"ABC",
        "FED",
        "GHI"};
    
    for (int i=0; i < sizeof(array)/sizeof(string); i++)
    {
        grid.push_back(array[i]);
        cout<<array[i]<<endl;
    }
    find = "ABCDEFGHI";
    cout <<find<<endl;
}

void Load1(vector <string> &grid, string &find)
{
    string array[]={"ABC",
 "FED",
 "GAI"};
    
    for (int i=0; i < sizeof(array)/sizeof(string); i++)
    {
        grid.push_back(array[i]);
        cout<<array[i]<<endl;
    }
    find = "ABCDEA";
    cout <<find<<endl;
}
void Load2(vector <string> &grid, string &find)
{
    string array[]={"ABABA",
 "BABAB",
 "ABABA",
 "BABAB",
 "ABABA"};
    
    for (int i=0; i < sizeof(array)/sizeof(string); i++)
    {
        grid.push_back(array[i]);
        cout<<array[i]<<endl;
    }
    find = "ABABABBA";
    cout <<find<<endl;
}
void Load3(vector <string> &grid, string &find)
{
    string array[]={"AA",
 "AA"};
    
    for (int i=0; i < sizeof(array)/sizeof(string); i++)
    {
        grid.push_back(array[i]);
        cout<<array[i]<<endl;
    }
    find = "AAAA";
    cout <<find<<endl;
}


void Load4(vector <string> &grid, string &find)
{
    string array[]={"AAAAA",
 "AAAAA",
 "AAAAA",
 "AAAAA",
 "AAAAA"};
    
    for (int i=0; i < sizeof(array)/sizeof(string); i++)
    {
        grid.push_back(array[i]);
        cout<<array[i]<<endl;
    }
    find ="AAAAAAAAAAA";
    cout <<find<<endl;
}
int main(int argc, char* argv[])
{
    WordPath word;
    vector <string> grid;
    string find;

    void(*LoadFn[])(vector <string> &grid, string &find)={
    Load,Load1,Load2,Load3,Load4};
    
    for ( int i = 0; i < sizeof(LoadFn)/sizeof(LoadFn[0]); i ++)
    {
        grid.clear();
        LoadFn[i](grid,  find);
        cout<<word.countPaths(grid,  find)<<endl;

    }

	return 0;
}