题目链接: http://poj.org/problem?id=1501
题意：给一个字符矩阵，再给“单词”，在矩阵中找到单词，输出单词首元素的坐标和末元素的坐标。
思路：是一道深搜，需要注意的是深搜的方向由始至终只能往一个方向，水平，
垂直还有斜线，而其他只需要理解好题目套模板即可做出，还有就是本题不需要
标记数组，因为深搜方向只有一个，途中不会碰到已访问的点。
下面是AC代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
using namespace std;
int n;
char mat[105][105];
char a[105];
bool flag;
int first_x,first_y,last_x,last_y;
void dfs(int x,int y,int i,int dx,int dy){
if(a[i]=='\0'){
flag=true;
last_x=dx;
last_y=dy;
return;
}
int nx=2*dx-x,ny=2*dy-y;
if(0<nx&&nx<=n&&0<ny&&ny<=n&&mat[nx][ny]==a[i]){
dfs(dx,dy,i+1,nx,ny);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf(" %c",&mat[i][j]);
}
}
while(scanf("%s",a)!=EOF){
if(a[0]=='0')
break;
flag=false;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[0]==mat[i][j]&&!flag){
//dfs(i,j,1);
first_x=i;first_y=j;
for(int dx=-1;dx<=1;dx++){
for(int dy=-1;dy<=1;dy++){
int nx=i+dx,ny=j+dy;
if(a[1]=='\0'){
flag=true;break;
}
if(mat[nx][ny]==a[1]&&!flag){
dfs(i,j,2,nx,ny);
}
}
}
}
}
}
if(flag){
printf("%d,%d %d,%d\n",first_x,first_y,last_x,last_y);
}
else{
printf("Not found\n");
}
}
return 0;
}