主要考虑最短路径问题,直接进行模拟,如果当前要走的点可以通过之前走过的点到达,那么就不是最短路。
#include<bits/stdc++.h>
using namespace std;
bool vis[210][210];
int step[5][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {0, 0}};
bool check(int x, int y) {
for(int i = 0; i < 5; i++)
if(vis[y + step[i][0]][x + step[i][1]])//要特判自身,如RL情况
return true;
return false;
}
int main(void) {
string a;
cin >> a;
int flag = 1, x = 101, y = 101;
for(int i = 0; i < a.size(); i++) {
if(a[i] == 'R') {
if(check(x + 1, y)) flag = 0;
vis[y][x] = true;
x++;
} else if(a[i] == 'L') {
if(check(x - 1, y)) flag = 0;
vis[y][x] = true;
x--;
} else if(a[i] == 'U') {
if(check(x, y - 1)) flag = 0;
vis[y][x] = true;
y--;
} else {
if(check(x, y + 1)) flag = 0;
vis[y][x] = true;
y++;
}
}
if(flag) cout << "YES";
else cout << "NO";
return 0;
}