解题思路:
我不喜欢啰嗦的代码,我用二维数组来做会让代码变得啰嗦,所以我用一维数组,那么上下左右走的方向数组可以换为一维数组的{-3, -1, 1, 3}
结构体内的代码我只需要当前的状态state以及我到当前状态走的步数step
注意事项:
如果我用一维数组的话,我需要判断我当前位置'.'的位置的合法性,如:我在3位置时我不能向左移动一步
因3是第二行第一个,向左移动会移动到第一行第三的位置,属于非法操作。
参考代码:
#include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <stack> #include <set> #include <vector> #include <cstdio> #include <map> #define LEN(array) ((sizeof(array)) / (sizeof(array[0]))) #define mo 1e9 + 7 #define ll long long int using namespace std; char mp[3][3]; string n, m; int lr[] = {-3, -1, 1, 3}; struct node{ string state; int step; node(string state, int step) : state(state), step(step){} }; int main(void){ int wz, res = 0; cin >> n >> m; set<string> s; queue<node> q; q.push({n, 0}); while (!q.empty()){ node now = q.front(); q.pop(); if (now.state == m){ cout << now.step << endl; return 0; } wz = now.state.find("."); for (int i = 0; i < 4; i++){ int new_wz = wz + lr[i]; if ((wz == 3 && lr[i] == -1) || (wz == 5 && lr[i] == 1) || (wz == 2 && lr[i] == 1) || (wz == 6 && lr[i] == -1) ) { new_wz = 0; continue; } if (new_wz >= 0 && new_wz <= 9){ string temp = now.state; swap(temp[wz], temp[new_wz]); if (!s.count(temp)){ q.push({temp, now.step + 1}); s.insert(temp); } } } } s.clear(); return 0; }
0.0分
17 人评分