首页 > 代码库 > POJ - 1077 Eight
POJ - 1077 Eight
题意:经典八数码问题
思路:HASH+BFS
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 500000; const int size = 1000003; typedef int State[9]; char str[30]; int state[9],goal[9]={1, 2, 3, 4, 5, 6, 7, 8, 0}; int dir[4][2]={{-1,0}, {1,0}, {0,-1}, {0,1}}; char path_dir[5]="udlr"; int st[MAXN][9],fa[MAXN],path[MAXN]; int head[size],next[MAXN]; int hash(State &s) { int v = 0; for (int i = 0; i < 9; i++) v = v*10 + s[i]; return v % size; } int insert(int s) { int h = hash(st[s]); int u = head[h]; while (u) { if (memcmp(st[u], st[s], sizeof(st[s])) == 0) return 0; u = next[u]; } next[s] = head[h]; head[h] = s; return 1; } int bfs() { memset(head, 0, sizeof(head)); fa[0] = path[0] = -1; int front=0,rear=1; memcpy(st[0], state, sizeof(state)); while (front < rear) { int *s = st[front]; if (memcmp(s, goal, sizeof(goal)) == 0) return front; int cnt; for (cnt = 0; cnt < 9; cnt++) if (s[cnt] == 0) break; int x = cnt/3, y = cnt%3; for (int i = 0; i < 4; i++) { int nx = x + dir[i][0]; int ny = y + dir[i][1]; int pos = nx*3+ny; if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) { int *ns = st[rear]; memcpy(ns, s, sizeof(int)*9); ns[cnt] = s[pos]; ns[pos] = 0; if (insert(rear)) { fa[rear] = front; path[rear] = i; rear++; } } } front++; } return -1; } void print(int u) { if (u) { print(fa[u]); printf("%c", path_dir[path[u]]); } } int main() { while (gets(str)) { int pos = 0; for (int i = 0; i < strlen(str); i++) { if (str[i] >= '0' && str[i] <= '9') state[pos++] = str[i] - '0'; else if (str[i] == 'x') state[pos++] = 0; } int ans = bfs(); if (ans != -1) { print(ans); printf("\n"); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。