Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-19

WordFind

| 10:10

問題文, SRM 232

Algorithm Tutorials -- How to Find a Solutionから。

worldListの単語は2次元配列gridのどこに隠れているのか。

171.37/250

class WordFind {
public:
    vector <string> findWords(vector <string> grid, vector <string> wordList) {
        const int H = grid.size();
        const int W = grid[0].size();
        vector <string> result(wordList.size(), "");
        for (int i = 0; i < wordList.size(); i++) {
            const int len = wordList[i].length();
            for (int r = 0; r < H; r++) {
                for (int c = 0; c < W; c++) {
                    const static int DIR_KINDS = 3;
                    const static int d[DIR_KINDS][2] = { {1,0}, {0,1}, {1,1} };
                    for (int j = 0; j < DIR_KINDS; j++) {
                        if (r+len*d[j][0] > H) continue;
                        if (c+len*d[j][1] > W) continue;
                        for (int k = 0; k < len; k++) {
                            if (wordList[i][k] != grid[r+k*d[j][0]][c+k*d[j][1]]) break;
                            if (k == len-1) {
                                ostringstream pos;
                                pos << r << " " << c;
                                result[i] = pos.str();
                                break;
                            }
                        }
                        if (result[i] != "") break;
                    }
                    if (result[i] != "") break;
                }
                if (result[i] != "") break;
            }
        }
        return result;
    }
};

YulyYuly2012/11/15 07:39You've hit the ball out the park! Incrieldbe!

ogjjxpbfedogjjxpbfed2012/11/16 05:36fSvQ3Y <a href="http://opkomgzlgoxs.com/">opkomgzlgoxs</a>

lllebwlllebw2012/11/17 05:07hx1oWF , [url=http://cdmmhpymcwvw.com/]cdmmhpymcwvw[/url], [link=http://zhernoocdpab.com/]zhernoocdpab[/link], http://pnimqosbodna.com/

fjpobhvgxctfjpobhvgxct2012/11/17 12:09CrZUBe <a href="http://gitnhbscrxca.com/">gitnhbscrxca</a>

wahfhgiylpwahfhgiylp2012/11/17 21:39wFLUSt , [url=http://eovjxcvzlscm.com/]eovjxcvzlscm[/url], [link=http://kpmczprsyijg.com/]kpmczprsyijg[/link], http://lqammhsdbqsp.com/