首页 > 试题广场 >

单词迷阵

[编程题]单词迷阵

热度指数：408 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

单词迷阵游戏就是从一个10x10的字母矩阵中找出目标单词，查找方向可以从左往右、从右往左、从上往下或者从下往上。例如下面的迷阵中包含quot等单词。
rmhlzxceuq
bxmichelle
mnnejluapv
caellehcim
xdydanagbz
xinairbprr
vctzevbkiz
jgfavqwjan
quotjenhna
iumxddbxnd
现给出一个迷阵，请你判断某个单词是否存在其中。

输入描述:

输入有多组数据。

每组数据包含两部分。

第一部分有10行，是一个10x10的字母矩阵。

第二部分第一行包含一个整数n (1≤n≤100)，紧接着n行，每行包含一个单词。单词的长度不会超过10。

输出描述:

对应每一个单词，如果它存在于迷阵之中，则输出“Yes”；否则输出“No”。

每一组数据之后输出一个空行作为分隔。

示例1

输入

rmhlzxceuq
bxmichelle
mnnejluapv
caellehcim
xdydanagbz
xinairbprr
vctzevbkiz
jgfavqwjan
quotjenhna
iumxddbxnd
7
dan
danz
brian
michelle
jen
jqi
paul
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
2
aaa
bbb

输出

Yes
Yes
Yes
Yes
Yes
Yes
Yes

Yes
No

算法知识视频讲解

C/C++

Cavs

建立Trie树。
先读入数据，在每行每列正向和反向建立Trie树；再检索。
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

#define INF 1000000
using namespace std;

struct Trie
{
	unordered_map<char,shared_ptr<Trie>> next;
	Trie(){}
};

void buildTrie(string s, shared_ptr<Trie> root)
{
	auto p = root;
	for (auto& c : s)
	{
		if (p->next.find(c) == p->next.end()) p->next[c] = make_shared<Trie>();
		p = p->next[c];
	}
}

bool checkTrie(string s, shared_ptr<Trie> root)
{
	auto p = root;
	for (auto& c : s)
	{
		if (p->next.find(c) == p->next.end()) return false;
		p = p->next[c];
	}
	return true;
}

int main(int argc, char** argv)
{
	//freopen("in.txt", "r", stdin);
	char c;
	vector<vector<char>> table(10, vector<char>(10));
	while ((c = getchar()) != EOF)
	{
		ungetc(c, stdin);
		for (int i = 0; i < 10; ++i)
		{
			for (int j = 0; j < 10; ++j)
			{
				c = getchar();
				table[i][j] = c;
			}
			getchar();
		}

		shared_ptr<Trie> root(new Trie);
		auto p = root;
		for (int i = 0; i < 10; ++i)
		{
			string s = "";
			for (int j = 0; j < 10; ++j) s += table[i][j];

			for (int j = 0; j < 10; ++j) buildTrie(s.substr(j), root);
			reverse(s.begin(), s.end());
			for (int j = 0; j < 10; ++j) buildTrie(s.substr(j), root);
		}

		for (int j = 0; j < 10; ++j)
		{
			string s = "";
			for (int i = 0; i < 10; ++i) s += table[i][j];

			for (int i = 0; i < 10; ++i) buildTrie(s.substr(i), root);
			reverse(s.begin(), s.end());
			for (int i = 0; i < 10; ++i) buildTrie(s.substr(i), root);
		}

		int n;
		string s;
		cin >> n;
		for (int i = 0; i < n; ++i)
		{
			cin >> s;
			if (checkTrie(s, root)) cout << "Yes" << endl;
			else cout << "No" << endl;
		}
		getchar();
	}

	return 0;
}

发表于 2017-07-13 22:58:48 回复(0)

doodle777

貌似不需要每组数据跟个空行。。。

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

#define N 10

bool search(vector<string> & table, string & str, int x, int y)
{
	int dir[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };

	for (int i = 0; i < 4; ++i) // 四个方向搜索
	{
		int nx = x, ny = y, j;
		for (j = 0; j < str.size(); ++j)
		{
			nx = x + dir[i][0] * j;
			ny = y + dir[i][1] * j;
			if (nx >= 0 && nx < N&&ny >= 0 && ny < N&&table[nx][ny] == str[j])
				continue;
			else break;
		}
		if (j == str.size()) return true;
	}
	return false;
}

bool solve(vector<string> & table, string & str)
{
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			if (search(table, str, i, j))
				return true;

	return false;
}

int main()
{
	vector<string> table(N);
	while (cin >> table[0])
	{
		for (int i = 1; i < N; ++i) cin >> table[i];
		int n; cin >> n;
		vector<string> search(n);
		for (int i = 0; i < n; ++i)
		{
			cin >> search[i];
			cout << (solve(table, search[i]) ? "Yes" : "No") << endl;
		}
//		cout << endl;
	}
	return 0;
}

发表于 2015-12-20 16:19:15 回复(0)

牛客210325号

package com.yzh.hehe;
import java.util.Scanner;


public class WordMiZheng {

    public static void main(String[] args) { 
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()) {
            char[][] arr=new char[10][];
            for (int i = 0; i < 10; i++) {
                arr[i]=scanner.nextLine().toCharArray();
            }
            int  n= Integer.valueOf(scanner.nextLine());
            String[] sArr=new String[n];
            for (int i = 0; i < n; i++) {
                sArr[i]=scanner.nextLine();
            }
            for (int i = 0; i < sArr.length; i++) {
                System.out.println(wordMiZheng(arr, sArr[i]));
            }
        }
        scanner.close();
    }


    private static String wordMiZheng(char[][] arr,String string) { 
        for(int  i=0;i<arr.length;i++){
            for (int j = 0; j < arr.length; j++) {
                if (conTainAtPoint(arr, i, j, string)) {
                    return "Yes";
                }
            }
        }
        return "No";
    }

    private static boolean conTainAtPoint(char[][] arr,int i,int j,String string) {
        StringBuilder stringBuilder=new StringBuilder(arr.length);
        int index=0;
        //从左向右
        for ( index = j; index < arr.length; index++) {
            stringBuilder.append(arr[i][index]);
        }
        for ( index = 0; index < j; index++){
            stringBuilder.append(arr[i][index]);
        }
        if (isContain(stringBuilder.toString(), string)) {
            return true;
        }else {

            stringBuilder.delete(0, arr.length);
        }
        //从右向左
        for ( index = j; index >= 0; index--) {
            stringBuilder.append(arr[i][index]);
        }
        for ( index = arr.length-1; index > j; index--){
            stringBuilder.append(arr[i][index]);
        }
        if (isContain(stringBuilder.toString(), string)) {
            return true;
        }else {

            stringBuilder.delete(0, arr.length);
        }

        //从上向下
        for ( index = i; index < arr.length; index++) {
            stringBuilder.append(arr[index][j]);
        }
        for ( index = 0; index < i; index++){
            stringBuilder.append(arr[index][j]);
        }
        if (isContain(stringBuilder.toString(), string)) {
            return true;
        }else {

            stringBuilder.delete(0, arr.length); 
        }

        //从下向上
        for ( index = i; index >= 0; index--) {
            stringBuilder.append(arr[index][j]);
        }
        for ( index = arr.length-1; index > i; index--){
            stringBuilder.append(arr[index][j]);
        }
        if (isContain(stringBuilder.toString(), string)) {
            return true;
        }else {
            return false;
        }
    }

    //判断字符串a中是否按顺序含有字符串b中的所有字符
    private static boolean isContain(String string1, String string2) {
        int index1=string1.length();
        int index2=0;
        char c=string2.charAt(0);
        for (int i = 0; i < index1; i++) {
            if (c==string1.charAt(i)) {
                index2++;
                if (index2==string2.length()) {
                    return true;
                }else {
                    c=string2.charAt(index2);
                }
            }
        }
        return false;
    }
}

发表于 2018-08-24 10:23:52 回复(0)

Java

詆調壹點

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			Character[][] ch = new Character[10][10];
			for (int i = 0; i < 10; i ++ ) {
				String s = sc.next();
				for (int j = 0; j < 10; j ++ ) {
					ch[i][j] = s.charAt(j);
				}
			}
			String[] res = new String[sc.nextInt()];
			for (int i = 0; i < res.length; i ++ ) {
				if(search(ch, sc.next())) res[i] = "Yes";
				else res[i] = "No";
			}
			for (String s:res) {
				System.out.println(s);
			}
		}
	}
	public static boolean search(Character[][] ch, String s) {
		int[][] direction = {{0, 1}, {0, - 1}, {1, 0}, { - 1, 0}};
		int l = 0;
		for (int i = 0; i < 10; i ++ ) {
			for (int j = 0; j < 10; j ++ ) {
				if(ch[i][j] == s.charAt(0)) {
					for (int k = 0; k < 4; k ++ ) {
						for (l = 0; l < s.length(); l ++ ) {
							int x = i + direction[k][0] * l;
							int y = j + direction[k][1] * l;
							if(x >= 0 && x < 10 && y >= 0 && y < 10 && ch[x][y] == s.charAt(l)) continue;
							else break;
						}
						if(l == s.length()) return true;
					}
				}
			}
		}
		return false;
	}
}

发表于 2016-10-11 02:01:19 回复(0)