若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1511: Where’s Waldorf?

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,210

题目描述

Given a m by n grid of letters, (), and a list of words, find the location in the grid at which the word can be found.

A word matches a straight, uninterrupted line of letters in the grid.A word can match the letters in the grid regardless of case (i.e. upper and lower case letters are to be treated as the same). The matching can be done in any of the eight directions either horizontally, vertically or diagonally through the grid.

输入

暂无

输出

暂无

样例输入

1

8 11
abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf
4
Waldorf
Bambi
Betty
Dagbert


样例输出

2 5
2 3
1 2
7 8


参考代码

#include<stdio.h>
#include<string.h>
char str[1000][1000];
char key[100][1000];
int main () 
{
    int n,i,j,k,u,h,w,num,len,ok,index;
    while (scanf("%d",&n) != EOF) 
    {
        for (u=0;u<n;u++) 
        {
            if (u) 
            {
                printf("n");
            }
            scanf("%d%d",&h,&w);
            for (i=0;i<h;i++) {
                scanf("%s",str[i]);
                len = strlen(str[i]);
                for (j=0;j<len;j++){
                    if (str[i][j]>='A'&&str[i][j]<='Z') {
                        str[i][j] +='a'-'A';
                    }
                }
            }
            scanf("%d",&num);
            for(i=0;i<num;i++) {
                scanf("%s",key[i]);
                len = strlen(key[i]);
                for (j=0;j<len;j++){
                    if (key[i][j]>='A'&&key[i][j]<='Z') {
                        key[i][j] +='a'-'A';
                    }
                }
            }
            len = strlen(key[i = 0]);
            for (j=1;j<=h;j++) {
                for (k=1;k<=w;k++) {
                    ok = 1;
                    if (str[j-1][k-1]==key[i][0]&&k>=len) {
                        for (index=0;index<len;index++) {
                            if (str[j-1][k-index-1]!=key[i][index]) ok = 0;
                        }
                        if (ok) {
                            printf("%d %dn",j,k);
                            j = 0;
                            i++;
                            if (i<num)
                            len = strlen(key[i]);
                            break;
                        }
                        if (j>=len) {
                            ok = 1;
                            for (index=0;index<len;index++) {
                                if (str[j-index-1][k-index-1]!=key[i][index]) ok = 0;
                            }
                            if (ok) {
                                printf("%d %dn",j,k);
                                j = 0;
                                i++;
                                if (i<num)
                                len = strlen(key[i]);
                                break;
                            }
                        } else if (h-j+1>=len) {
                            ok = 1;
                            for (index=0;index<len;index++) {
                                if (str[j+index-1][k-index-1]!=key[i][index]) ok = 0;
                            }
                            if (ok) {
                                printf("%d %dn",j,k);
                                j = 0;
                                i++;
                                if (i<num)
                                len = strlen(key[i]);
                                break;
                            }
                        }
                    } if (str[j-1][k-1]==key[i][0]&&w-k+1>=len) {
                        ok = 1;
                        for (index=0;index<len;index++) {
                            if (str[j-1][k+index-1]!=key[i][index]) ok = 0;
                        }
                        if (ok) {
                            printf("%d %dn",j,k);
                            j = 0;
                            i++;
                            if (i<num)
                            len = strlen(key[i]);
                            break;
                        }
                        if (j>=len) {
                            ok = 1;
                            for (index=0;index<len;index++) {
                                if (str[j-index-1][k+index-1]!=key[i][index]) ok = 0;
                                }
                                if (ok) {
                                    printf("%d %dn",j,k);
                                    j = 0;
                                    i++;
                                    if (i<num)
                                    len = strlen(key[i]);
                                    break;
                                }
                        }
                        if (h-j+1>=len) {
                            ok = 1;
                            for (index=0;index<len;index++) {
                                if (str[j+index-1][k+index-1]!=key[i][index]) ok = 0;
                            }
                            if (ok) {
                                printf("%d %dn",j,k);
                                j = 0;
                                i++;
                                if (i<num)
                                len = strlen(key[i]);
                                break;
                            }
                        }
                    } if (str[j-1][k-1]==key[i][0]&&j>=len) {
                        ok = 1;
                        for (index=0;index<len;index++) {
                            if (str[j-index-1][k-1]!=key[i][index]) ok = 0;
                        }
                        if (ok) {
                            printf("%d %dn",j,k);
                            j = 0;
                            i++;
                            if (i<num)
                            len = strlen(key[i]);
                            break;
                        }
                    } if (str[j-1][k-1]==key[i][0]&&h-j+1>=len) {
                        ok = 1;
                        for (index=0;index<len;index++) {
                            if (str[j+index-1][k-1]!=key[i][index]) ok = 0;
                        }
                        if (ok) {
                            printf("%d %dn",j,k);
                            j = 0;
                            i++;
                            if (i<num)
                            len = strlen(key[i]);
                            break;
                        }
                    }
                }
            }
        }
    }
    return 0;
}

解析

暂无

hustoj

发表评论 取消回复

电子邮件地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Skip Dreams孤独患者 原站点
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist