文字列の八方向検索 in C++ DouKaku?

与えられた矩形状の文字列中に存在する文字列"ウオリ"の位置を全て出力するプログラムを
書いてください。
文字列の検索方向は八方全てで、また連続している（左右や上下の境界をまたがない）ものを
対象とします。出力は起点"ウ"の座標と方向のリストにしてください。

サンプル入力：

リオウウリウ
ウオリウオリ
オリリオリウ
リリオオウオ

サンプル出力：

(2, 0), 左
(0, 1), 右
(0, 1), 下
(3, 1), 右
(4, 3), 左上

--
より一般には、任意の検索文字列への対応も考えてみてください。

全角じゃないけど。反転した比較文字列をつくって、４方向（右方向＋下方向）の文字列チェック×２で、８方向...になってるとおもう....orz

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

void output(int x, int y, std::string v)
{
    std::cout << "(" << x << "," << y << "), " << v.c_str() << std::endl;
}

void search8way(std::vector<std::string> lines, std::string str)
{
    if (str.empty() != false)
        return;

    std::string rstr(str);
    reverse(rstr.begin(), rstr.end());

    int nLen = (int)str.size();
    char cs = str[0];
    char ce = str[nLen - 1];

    int x = 0;
    for (int y = 0; y < (int)lines.size(); y++)
    {
        std::string line = lines[y];
        for (int x = 0; x < (int)line.size(); x++) 
        {
            char c = line[x];
            if ((c != cs) && (c != ce))
                continue;

            std::string strDL(""); strDL += c;
            std::string strDD(""); strDD += c;
            std::string strDR(""); strDR += c;
            for (int d = 1; (d < nLen) && (y + d < (int)lines.size()); d++)
            {
                std::string buff = lines[y + d];
                if ( x      < (int)buff.size()                ) { strDD += buff[x    ]; }
                if ((x - d) < (int)buff.size() && (x - d >= 0)) { strDL += buff[x - d]; }
                if ((x + d) < (int)buff.size()                ) { strDR += buff[x + d]; }
            }

            if (c == cs)
            {
                if (line.compare(x, nLen, str) == 0) { output(x, y, "右"); }
                if (strDL.compare(str) == 0) { output(x, y, "左下"); }
                if (strDD.compare(str) == 0) { output(x, y, "下"  ); }
                if (strDR.compare(str) == 0) { output(x, y, "右下"); }
            }
            if (c == ce)
            {
                if (line.compare(x, nLen, rstr) == 0) { output(x + (nLen - 1), y, "左"); }
                if (strDL.compare(rstr) == 0) { output(x - (nLen - 1), y + (nLen - 1), "右上"); }
                if (strDD.compare(rstr) == 0) { output(x             , y + (nLen - 1), "上");   }
                if (strDR.compare(rstr) == 0) { output(x + (nLen - 1), y + (nLen - 1), "左上"); }
            }
        }
    }
}

int main(int argc, char* argv[])
{
    std::vector<std::string> lines;
    lines.push_back("ABCBCBCBA");
    lines.push_back("ABCBBBCBA");
    lines.push_back("ABCBABCBA");
    lines.push_back("ABCBBBCBA");
    lines.push_back("ABCBCBCBA");
    search8way(lines, "ABC");
    return 0;
}

方法は殆ど変わってないのですが。下方向へのチェックだと、入力がファイルや標準入力だった時につぶしがきかない（行を先読みしないといけない）ので、上方向に修正。

void output(int x, int y, std::string v)
{
    std::cout << "(" << x << "," << y << "), " << v.c_str() << std::endl;
}

void search8way(std::vector<std::string> lines, std::string str)
{
    if (str.empty() != false)
        return;

    std::string rstr(str);
    std::reverse(rstr.begin(), rstr.end());

    int nLen = (int)str.size();
    char cs = str[0];
    char ce = str[nLen - 1];

    for (int y = 0; y < (int)lines.size(); y++)
    {
        std::string line = lines[y];

        for (int x = 0; x < (int)line.size(); x++) 
        {
            if ((line[x] != cs) && (line[x] != ce))
                continue;

            std::string strLU(""); strLU += line[x];
            std::string strUP(""); strUP += line[x];
            std::string strRU(""); strRU += line[x];
            for (int d = 1; (d < nLen) && ((y - d) >= 0); d++)
            {
                std::string buff = lines[y - d];
                if (((int)buff.size() > (x - d)) && ((x - d) >= 0))
                    strLU += buff[x - d];
                if ((int)buff.size() > x)
                    strUP += buff[x];
                if ((int)buff.size() > (x + d))
                    strRU += buff[x + d];
            }

            if (line[x] == cs)
            {
                if (line.compare(x, nLen, str) == 0)
                    output(x, y, "右");

                if (strLU.compare(str) == 0) { output(x, y, "左上"); }
                if (strUP.compare(str) == 0) { output(x, y, "上"  ); }
                if (strRU.compare(str) == 0) { output(x, y, "右上"); }
            }
            if (line[x] == ce)
            {
                if (line.compare(x, nLen, rstr) == 0) 
                    output(x + (nLen - 1), y, "左");

                if (strRU.compare(rstr) == 0)
                    output(x + (nLen - 1), y - (nLen - 1), "左下");
                if (strUP.compare(rstr) == 0)
                    output(x             , y - (nLen - 1), "下");
                if (strLU.compare(rstr) == 0)
                    output(x - (nLen - 1), y - (nLen - 1), "右下");
            }
        }
    }
}

DouKaku?

文字列の八方向検索

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq