本文共 1529 字，大约阅读时间需要 5 分钟。
直接bfs即可,取最后一个状态
#include #include #include #include #include using namespace std;struct Dir{ int x, y;};struct Node{ int x, y; string str = ""; string steps = "";};char st[] = { 'U', 'D', 'L', 'R' };Dir dir[] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };queue q;const int N = 5;string ans = "";string ansStep = "";int index(int x, int y){ return y * 3 + x;}void bfs(map repeatMaps){ while (!q.empty()) { Node node = q.front(); q.pop(); int curZero = index(node.x, node.y); string curStr = node.str; for(int i = 0; i < 4; i++) { int nx = node.x + dir[i].x; int ny = node.y + dir[i].y; if(nx < 0 || ny < 0 || nx > 2 || ny > 2) continue; //nextstr string nextStr(curStr); swap(nextStr[index(nx, ny)], nextStr[curZero]); if(repeatMaps.find(nextStr) == repeatMaps.end()) { //未重复 Node n; n.str = nextStr; n.x = nx; n.y = ny; n.steps = node.steps + st[i]; q.push(n); ans = nextStr; ansStep = n.steps; repeatMaps[nextStr] = 0; } } }}int main(){ freopen("d://1.text", "r", stdin); //3x3图 //目标图 int n; cin >> n; int t =1; while (n--) { if(t!=1) cout< > k; str += k+'0'; if(k == 0) { y = i; x = j; } } Node init; init.steps = ""; init.str = str; init.x = x; init.y = y; q.push(init); map repeatMaps; repeatMaps[str] = 0; bfs(repeatMaps); cout<<"Puzzle #"< <
转载于:https://www.cnblogs.com/shuiyonglewodezzzzz/p/9387515.html