题目链接： (dfs)
求从起点到终点转方向不超过两次是否有解，，好水啊，感觉自己代码好搓。。
#include#include #include #include #include #include #include #include #define CLR(a,b) memset((a),(b),sizeof((a)))using namespace std;typedef long long ll;const int N = 1005;int n, m;int sx, sy, ex, ey;int flag;char s[N][N];int vis[N][N][5][5];void dfs(int x, int y, int d, int turn) { //上下：d = 1，左右：d = 2 if(turn > 2 || vis[x][y][d][turn]) return; if(x == ex && y == ey) { flag = true; return; } vis[x][y][d][turn] = 1; if(x-1 >= 0 && s[x-1][y] != '*' && !vis[x-1][y][1][turn+(d==2)]) { dfs(x-1, y, 1, turn + (d==2)); } if(x+1 < n && s[x+1][y] != '*' && !vis[x+1][y][1][turn+(d==2)]) { dfs(x+1, y, 1, turn + (d==2)); } if(y-1 >= 0 && s[x][y-1] != '*' && !vis[x][y-1][2][turn+(d==1)]) { dfs(x, y-1, 2, turn + (d==1)); } if(y+1 < m && s[x][y+1] != '*' && !vis[x][y+1][2][turn+(d==1)]) { dfs(x, y+1, 2, turn + (d==1)); }}int main() { int i, j; scanf("%d%d ", &n, &m); for(i = 0; i < n; ++i) { scanf("%s", s[i]); for(j = 0; j < m; ++j) { if(s[i][j] == 'S') {sx = i; sy = j;} else if(s[i][j] == 'T') {ex = i; ey = j;} } } flag = 0; CLR(vis, 0); dfs(sx, sy, 0, 0); if(flag) puts("YES"); else puts("NO"); return 0;}