UVA10010 - Where's Waldorf?

问题描述

输入n*m字符矩阵，有k个字符串（全部均在字符矩阵中），判断这些字符串在字符矩阵中开始的哪个位置。
           

思路

暴力搜索，DFS（深度优先搜索）。从字符矩阵的第一个位置开始往它的八个方向开始比对，如果字符不一样，则往另一个方向进行查找，如果字符串不一样，则从字符矩阵的第二个位置开始继续查找，如果字符串相同，则输出该字符矩阵的下标。

代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
using namespace std;
char s[][];
char f[];
int dir[][]={{-,-},{-,},{-,},{,},
                {,},{,},{,-},{,-}};
int x,y,n,m;
void dfs(int a,int b,char f[])
{
    char g[];
    int i,j,k;
    int len=strlen(f);
    for(i=;i<n;i++)
    {
        for(j=;j<m;j++)
        {
            if(s[i][j]!=f[])
                continue;
            for(k=;k<;k++)
            {
                g[]=s[i][j];
                int dx=i+dir[k][];
                int dy=j+dir[k][];
                int t=;
                while(dx>=&&dx<n&&dy>=&&dy<m)
                {
                    g[t++]=s[dx][dy];
                    if(t==len)
                        break;
                    dx+=dir[k][];
                    dy+=dir[k][];
                }
                g[t]='\0';
                if(strcmp(g,f)==)
                {
                    x=i+;
                    y=j+;
                    return;
                }
            }
        }
    }
}
int main()
{
    int t,i,j,k;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(i=;i<n;i++)
        {
            scanf("%s",s[i]);
            for(j=;j<m;j++)
                s[i][j]=tolower(s[i][j]);
        }
        cin>>k;
        for(i=;i<k;i++)
        {
            scanf("%s",f);
            for(j=;f[j]!='\0';j++)
                f[j]=tolower(f[j]);
            x=y=;
            dfs(x,y,f);
            cout<<x<<" "<<y<<endl;
        }
        if(t)
            cout<<endl;

    }
    return ;
}