dfs深度优先搜索-象棋走马步
解题思路：
dfs深搜，对马可以走的八个方向用一个dir[4][2]的数组存储，然后再依次深搜，如果可以走到就返回true，否则返回false；然后回溯上一个节点，直到看是否有没有走到终点‘T’，如果有，就f=true，否则就没有false；
代码：
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#include<string.h>
char s[10][10];
bool f;
bool vis[10][10];
int dir[8][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
bool in(int x,int y){
return 0<=x&&x<10&&0<=y&&y<9;
}
void dfs(int x,int y){
vis[x][y]=true;
if(f){
return;
}
if(s[x][y]=='T'){
f=true;
return;
}
for(int i=0;i<10;i++){
int tx=x+dir[i][0];
int ty=y+dir[i][1];
if(in(tx,ty)&&s[tx][ty]!='#'&&!vis[tx][ty]){
dfs(tx,ty);
}
}
}
int main(){
int x,y;
for(int i=0;i<10;i++){
scanf("%s",s[i]);
}
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
if(s[i][j]=='S'){
x=i;
y=j;
}
}
}
dfs(x,y);
if(f){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
return 0;
}
