1

Cを介して文字のマトリックス内の特定の単語を検索しようとしましたが、解決策を見つけることができませんでした。

例：文字のマトリックス（3 * 9）でINTELLIGENTという単語を検索する必要があるとします（マトリックスから文字を選択して文を形成すると、同じ文を形成するために再度選択することはできません。任意のセルからそのすべての隣接セルへのパス。隣接セルはエッジまたはコーナーを共有できます。）

IIIINN.LI  
.... TTEGL  
.....ネリ

出力：はい（INTELLIGENTという単語が見つかります）上記の問題の解決策を教えてください!!!!

4

4 に答える 4

1

深さ優先検索を使用します。

これは、再帰アルゴリズムを使用して行うことができます。最初の文字を含むすべての (使用されていない) 場所を見つけ、隣接する正方形の 1 つから開始して、残りのボードで残りの単語を見つけることができるかどうかを確認します。

于 2012-05-18T06:50:39.823 に答える
0 
#include <stdio.h>

char Matrix[3][9] = {
    { 'I','I','I','I','N','N','.','L','I'},
    { '.','.','.','.','T','T','E','G','L'},
    { '.','.','.','.',',','N','E','L','I'}
};
char Choice[3][9] = { { 0 }, { 0 }, { 0 } };
const char WORD[] = "INTELLIGENT";
const int  Len = sizeof(WORD)-1;
int Path[sizeof(WORD)-1] = { 0 };

char get(int row, int col){
    if(1 > col || col > 9) return '\0';
    if(1 > row || row > 3) return '\0';
    if(Choice[row-1][col-1] || Matrix[row-1][col-1] == '.')
        return '\0';
    else
        return Matrix[row-1][col-1];
}

#define toLoc(r, c) (r)*10+(c)
#define getRow(L) L/10
#define getCol(L) L%10

int search(int loc, int level){
    int r,c,x,y;
    char ch;
    if(level == Len) return 1;//find it
    r = getRow(loc);
    c = getCol(loc);
    ch = get(r,c);
    if(ch == 0 || ch != WORD[level]) return 0;
    Path[level]=toLoc(r,c);
    Choice[r-1][c-1] = 'v';//marking
    for(x=-1;x<=1;++x){
        for(y=-1;y<=1;++y){
            if(search(toLoc(r+y,c+x), level + 1)) return 1;
        }
    }
    Choice[r-1][c-1] = '\0';//reset
    return 0;
}

int main(void){
    int r,c,i;
    for(r=1;r<=3;++r){
        for(c=1;c<=9;++c){
            if(search(toLoc(r,c), 0)){
                printf("YES\nPath:");
                for(i=0;i<Len;++i){
                    printf("(%d,%d)", getRow(Path[i]), getCol(Path[i]));
                }
                printf("\n");
                return 0;
            }
        }
    }
    printf("NO\n");
    return 0;
}
于 2012-05-18T12:13:38.873 に答える
0

私はこれがあなたの言いたいことだと思います....あなたが現在提供されているものよりも簡単に思えるので、質問を誤解したかもしれません.

Numpy を使用して、任意の配列を単一の文字リストに再形成し、検索語のマスクと入力リストのコピーを作成します。マスクを更新しながら、検索する各文字にチェックを入れます。

numpy を np としてインポート
輸入コピー

def findInArray(I,Word):
    M=[I の x のリスト(x)]

    M=list(np.ravel(M))

    print "開始文字: %s"%"".join(M)

    Mask=[False]*len(Word)

    T = コピー.コピー(M)

    enumerate(Word) の n、v の場合:
        試す：
            p=T.index(v)
        ValueError を除く:
            合格
        そうしないと：
            T[p]=''
            マスク[n]=True

    print "残りの文字: %s"%"".join(T)            
    if all(Mask):print "Found %s"%Word
    else:print "%s not Found"%Word

    「\n」を出力

    すべてを返す(マスク)


I=["IIIINN.LI","....TTEGL",".....NELI"]

findInArray(I,"インテル")
findInArray(I,"インテリジェント")
findInArray(I,"インテリジェンス")

出力例

開始文字: IIIINN.LI....TTEGL.....NELI 残りの
文字: IIIN.I....TGL.....NELI
発見インテル

開始する文字: IIIINN.LI....TTEGL.....NELI 残りの
文字: II.I........NLI
Found INTELLIGENT

最初の文字: IIIINN.LI....TTEGL.....NELI 残りの
文字: II.I....T.....NLI
INTELLIGENCE not Found

于 2012-05-19T07:02:47.857 に答える
0 
#include <stdio.h>

#define ROW 1
#define COL 11

char Matrix[ROW][COL] = { { 'I','N','T','E','L','L','I','G','E', 'N', 'T'} };
char Choice[ROW][COL] = { { 0 } };
const char WORD[] = "INTELLIGENT";
const int  Len = sizeof(WORD)-1;
int Path[sizeof(WORD)-1] = { 0 };

char get(int row, int col){
    if(1 > col || col > COL) return '\0';
    if(1 > row || row > ROW) return '\0';
    if(Choice[row-1][col-1] || Matrix[row-1][col-1] == '.')
        return '\0';
    else
        return Matrix[row-1][col-1];
}

#define toLoc(r, c) (r)*16+(c)
#define getRow(L) L/16
#define getCol(L) L%16

int search(int loc, int level){
    int r,c,x,y;
    char ch;
    if(level == Len) return 1;//find it
    r = getRow(loc);
    c = getCol(loc);
    ch = get(r,c);
    if(ch == 0 || ch != WORD[level]) return 0;
    Path[level]=toLoc(r,c);
    Choice[r-1][c-1] = 'v';//marking
    for(x=-1;x<=1;++x){
        for(y=-1;y<=1;++y){
            if(search(toLoc(r+y,c+x), level + 1)) return 1;
        }
    }
    Choice[r-1][c-1] = '\0';//reset
    return 0;
}

int main(void){
    int r,c,i;
    for(r=1;r<=ROW;++r){
        for(c=1;c<=COL;++c){
            if(search(toLoc(r,c), 0)){
                printf("YES\nPath:");
                for(i=0;i<Len;++i){
                    printf("(%d,%d)", getRow(Path[i]), getCol(Path[i]));
                }
                printf("\n");
                return 0;
            }
        }
    }
    printf("NO\n");
    return 0;
}
于 2012-05-22T10:55:28.290 に答える