1014: The Matrix
--------------------------------------------------------------------------------
Status In/Out TIME Limit MEMORY Limit Submit Times Solved Users JUDGE TYPE
stdin/stdout 3s 8192K 1233 351 Standard
Given a matrix of characters, and a list of words, output whether or not each word is present in the matrix. Words may appear forwards and backwards. They may appear horizontally, vertically, and diagonally.
Input
The matrix, followed by a list of words. Only lower case characters will be used. Each matrix will be square, and contain no more than 20 characters on a side. The string XXX denotes the end of input.
Output
For each word, report whether or not it is present in the matrix. If it is present, output should read “<word> is in the matrix.” If it is not present, output should read “<word> is not in the matrix.”, where <word> is the word in question.
Sample Input
applexy
pxlhjke
edeqgfl
xocgvpl
gghnmnn
tahuupu
qdgbywb
apple
axe
apex
cat
car
hat
computer
gum
XXX
Sample Output
apple is in the matrix.
axe is in the matrix.
apex is in the matrix.
cat is not in the matrix.
car is not in the matrix.
hat is in the matrix.
computer is not in the matrix.
gum is in the matrix.
给出此题的链接http://acm.jlu.edu.cn/joj/showproblem.php?pid=1014
我的代码是：
#include <iostream>
using namespace std;
bool up(int,int,int);
bool down(int,int,int);
bool left(int,int,int);
bool right(int,int,int);
bool ul(int,int,int);
bool ur(int,int,int);
bool dl(int,int,int);
bool dr(int,int,int);
char a[19][19]; //存储矩阵
char q[19]; //存储要查询的字符串
int m;
bool tag=0;
int main()
{
cin>>a[0];
m=strlen(a[0]);
for (int i=1;i<m;i++)
{
cin>>a[i];
}
while (cin>>q && strcmp(q,"XXX"))
{
int len=strlen(q);
for (int i=0;i<m;i++)
for (int j=0;j<m;j++)
if (q[0]==a[i][j])
{
tag=(up(i,j,len)||down(i,j,len)||left(i,j,len)||right(i,j,len)||ul(i,j,len)||ur(i,j,len)||dl(i,j,len)||dr(i,j,len));
if (tag==1)
goto a1;
}
a1:if (tag==0)
cout<<q<<" is not in the matrix."<<endl;
}
}
bool up(int posx,int posy,int n)
{
int i=posx;
int j=posy;
char cq[19];
if (i+1>=n)
{
int last=i-n;
int k=0;
for (;i>last;i--,k++)
cq[k]=a[i][j];
cq[k]='\0';
if(strcmp(cq,q)==0)
{
cout<<q<<" is in the matrix."<<endl;
return 1;
}
else
return 0;
}
else
return 0;
}
bool down(int posx,int posy,int n)
{
int i=posx;
int j=posy;
char cq[19];
if (m-i>=n)
{
int last=i+n;
int k=0;
for (;i<last;i++,k++)
cq[k]=a[i][j];
cq[k]='\0';
if(strcmp(cq,q)==0)
{
cout<<q<<" is in the matrix."<<endl;
return 1;
}
else
return 0;
}
else
return 0;
}
bool left(int posx,int posy,int n)
{
int i=posx;
int j=posy;
char cq[19];
if (j+1>=n)
{
int last=j-n;
int k=0;
for (;j>last;j--,k++)
cq[k]=a[i][j];
cq[k]='\0';
if(strcmp(cq,q)==0)
{
cout<<q<<" is in the matrix."<<endl;
return 1;
}
else
return 0;
}
else
return 0;
}
bool right(int posx,int posy,int n)
{
int i=posx;
int j=posy;
char cq[19];
if (m-j>=n)
{
int last=j+n;
int k=0;
for (;j<last;j++,k++)
cq[k]=a[i][j];
cq[k]='\0';
if(strcmp(cq,q)==0)
{
cout<<q<<" is in the matrix."<<endl;
return 1;
}
else
return 0;
}
else
return 0;
}
bool ul(int posx,int posy,int n)
{
int i=posx;
int j=posy;
char cq[19];
if (i+1>=n&&j+1>=n)
{
int last=i-n;
int k=0;
for (;i>last;i--,j--,k++)
cq[k]=a[i][j];
cq[k]='\0';
if(strcmp(cq,q)==0)
{
cout<<q<<" is in the matrix."<<endl;
return 1;
}
else
return 0;
}
else
return 0;
}
bool ur(int posx,int posy,int n)
{
int i=posx;
int j=posy;
char cq[19];
if (m-j>=n&&i+1>=n)
{
int last=j+n;
int k=0;
for (;j<last;i--,j++,k++)
cq[k]=a[i][j];
cq[k]='\0';
if(strcmp(cq,q)==0)
{
cout<<q<<" is in the matrix."<<endl;
return 1;
}
else
return 0;
}
else
return 0;
}
bool dl(int posx,int posy,int n)
{
int i=posx;
int j=posy;
char cq[19];
if (j+1>=n&&m-i>=n)
{
int last=i+n;
int k=0;
for (;i<last;i++,j--,k++)
cq[k]=a[i][j];
cq[k]='\0';
if(strcmp(cq,q)==0)
{
cout<<q<<" is in the matrix."<<endl;
return 1;
}
else
return 0;
}
else
return 0;
}
bool dr(int posx,int posy,int n)
{
int i=posx;
int j=posy;
char cq[19];
if (m-i>=n&&m-j>=n)
{
int last=j+n;
int k=0;
for (;j<last;i++,j++,k++)
cq[k]=a[i][j];
cq[k]='\0';
if(strcmp(cq,q)==0)
{
cout<<q<<" is in the matrix."<<endl;
return 1;
}
else
return 0;
}
else
return 0;
}
思想就是找出要查询的字符串第一个数的坐标，然后向8个方向分别查找，程序在自己机器上运行没问题，可是提交的时候出现超时，请牛人指点
