中国象棋博大精深，其中马的规则最为复杂，也是最难操控的一颗棋子。我们都知道象棋中马走\"日\"，比如在 (2, 4)位置的一个马，跳一步能到达的位置有 (0, 3)，(0,5)，(1,2)，(1,6)，(3,2)，(3,6)，(4, 3)，(4,5)。
蒜头君正在和花椰妹下棋，蒜头君正在进行战略布局，他需要把在 (x,y) 位置的马跳到 (x′,y′) 位置，以达到威慑的目的。
但是棋盘大小有限制，棋盘是一个 10×9 的网格，左上角坐标为(0,0)，右下角坐标为(9,8)，马不能走出棋盘，并且有些地方已经有了棋子，马也不能跳到有棋子的点。蒜头君想知道，在不移动其他棋子的情况下，能否完成他的战略目标。
输入格式
输入一共 10 行，每行一个长度为 9 的字符串。
输入表示这个棋盘，我们用'.'表示空位置，用'#'表示该位置有棋子，用'S'表示初始的马的位置，用'T'表示马需要跳到的位置。\n\n输入保证一定只存在一个'S'和一个'T'。
输出格式
如果在不移动其他棋子的情况下，马能从'S'跳到'T'，那么输出一行\"Yes\"，否则输出一行\"No\"。
#include <iostream> #include <string> using namespace std; string a[10]; //马的八种走法 int b[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}}; bool c[10][10]; bool in(int x,int y){ return x>=0 && x<10 && y>=0 && y<9; } bool f; bool dfs(int x,int y){ int tx,ty; if(a[x][y]=='T'){ return true; } a[x][y]='m'; c[x][y]=1; for(int i=0;i<8;i++){ tx=x+b[i][0]; ty=y+b[i][1]; if(in(tx,ty) && a[tx][ty]!='#'&& !c[tx][ty]){ if(dfs(tx,ty)){ return true; } } } a[x][y]='.'; return false; } int main(){ int x,y; for(int i=0;i<10;i++){ cin>>a[i]; } for(int i=0;i<10;i++){ for(int j=0;j<9;j++){ if(a[i][j]=='S'){ x=i; y=j; } } } if(dfs(x,y)){ cout<<"yes"<<endl; for(int i=0;i<10;i++){ cout<<a[i]<<endl; } } else{ cout<<"no"<<endl; } return 0; }
运行结果如下：
m代表马走过的位置
