东莞企业网站后缀,网站建设客户定位,英国做暧小视频网站,设计分享网站题目#xff1a;
马走日#xff0c;不考虑别马脚#xff0c;问马能否从S走到T#xff0c;其中‘#’表示不能落下#xff0c;‘.’表示能落下 输入#xff1a;
.#....#S#
..#.#.#..
..##.#..#
......##.
...T.....
...#.#...
...#.....
...###...
.........
.##......输…题目
马走日不考虑别马脚问马能否从S走到T其中‘#’表示不能落下‘.’表示能落下 输入
.#....#S#
..#.#.#..
..##.#..#
......##.
...T.....
...#.#...
...#.....
...###...
.........
.##......输出
Yes分析与解答
如果在for的下面加上回溯vis[x][y]false;时间超时有的时候如果只用考虑能否到达而不用考虑具体路径只用增加一个全局变量f能走到的话就f就为true了不能的话dfs函数全部遍历一遍也没改变f此时f就是初始的false。不用加上回溯。
凭感觉来说整个完整搜索树的时间要小于通过回溯找到路径的最坏的可能时间。所以说如果只用考虑能否到达那就不用回溯。
代码
#includeiostream
#includestring
using namespace std;
string maze[12];
bool vis[15][15];
int dir[8][2]{{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};//行,列
bool f;
int in (int x,int y){if(0xx100yy9){return 1;}else return 0;
}
void dfs(int x,int y){vis[x][y]true;if(f){return ;}if(maze[x][y]T){ftrue;return ;}for(int i0;i8;i){int txxdir[i][0];int tyydir[i][1];if(in(tx,ty)maze[tx][ty]!#!vis[tx][ty]){dfs(tx,ty);}}
}int main(){for(int i0;i10;i){cinmaze[i];} int x,y;for(int i0;i10;i){for(int j0;j9;j){if(maze[i][j]S){xi;yj;}}}dfs(x,y);if(f){coutYes;}else{coutNo;}}
