题目描述
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;
}
解析
暂无