原题传送门思路： 输出三种结果： 摸左边墙走，摸右边墙走，最短路线
注意点：方向是按自己当前方向来算的，第一个路线的方向循环是左上右下，第二个路线的循环是右上左下。
以左路线为例： 思考得之，进入方格的方向是上一格前进时朝向的方向，而当前应该前进的方向是循环内的上一方向。即：如果此时进入方向N，然后应该先向W前进。
DFS运算前两个，BFS运算最短路径
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; /***************************************/ #define ll long long #define int64 __int64 /***************************************/ const int INF = 0x7f7f7f7f; int w, h; int leftMoveY[4] = {-1, 0, 1, 0}; int leftMoveX[4] = {0, -1, 0, 1}; //左上右下 int rightMoveY[4] = {1, 0, -1, 0}; int rightMoveX[4] = {0, -1, 0, 1}; //右上左下 char chess[50][50]; int vis[50][50]; int leftStep, rightStep, shortStep; int leftStepTemp, rightStepTemp; int shortStepTemp[50][50]; void leftDFS(int x, int y, int d) { if (chess[x][y] == 'E') { leftStep = leftStepTemp; return; } int x1, y1; if (d == 0) d = 3; else d--; for (int i = d; i < 4; i++) { x1 = x + leftMoveX[i]; y1 = y + leftMoveY[i]; if (x1 > 0 && x1 <= h && y1 > 0 && y1 <= w && chess[x1][y1] != '#') { leftStepTemp++; leftDFS(x1, y1, i); } if (leftStep) return; if (i == 3) i = -1; } } void rightDFS(int x, int y, int d) { if (chess[x][y] == 'E') { rightStep = rightStepTemp; return; } int x1, y1; if (d == 0) d = 3; else d--; for (int i = d; i < 4; i++) { x1 = x + rightMoveX[i]; y1 = y + rightMoveY[i]; if (x1 > 0 && x1 <= h && y1 > 0 && y1 <= w && chess[x1][y1] != '#') { rightStepTemp++; rightDFS(x1, y1, i); } if (rightStep) return; if (i == 3) i = -1; } } void BFS(int x, int y) { queue<int> Q; Q.push(x); Q.push(y); int x1, y1; while (!Q.empty()) { x1 = Q.front(); Q.pop(); y1 = Q.front(); Q.pop(); if (vis[x1][y1] == 1) continue; vis[x1][y1] = 1; for (int i = 0; i < 4; i++) { int x2 = x1 + leftMoveX[i]; int y2 = y1 + leftMoveY[i]; if (!vis[x2][y2] && ((chess[x2][y2] == '.') || (chess[x2][y2] == 'E'))) { Q.push(x2); Q.push(y2); shortStepTemp[x2][y2] = shortStepTemp[x1][y1] + 1; if (chess[x2][y2] == 'E') { shortStep = shortStepTemp[x2][y2]; return; } } } } } int main() { int n; cin >> n; while (n--) { memset(chess, 0, sizeof(chess)); memset(vis, 0, sizeof(vis)); memset(shortStepTemp, 0, sizeof(shortStepTemp)); leftStep = rightStep = shortStep = leftStepTemp = rightStepTemp = 0; cin >> w >> h; int sx, sy; for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) { cin >> chess[i][j]; if (chess[i][j] == 'S') sx = i, sy = j; } leftDFS(sx, sy, 1); rightDFS(sx, sy, 1); BFS(sx, sy); cout << leftStep + 1 << ' ' << rightStep + 1 << ' ' << shortStep + 1 << endl; } system("pause"); return 0; }转载于:https://www.cnblogs.com/ruoh3kou/p/9893453.html
