BFS+查重
因为通过不同的路径到达同一个点会产生不同的串，不具有唯一性，
所以查重不再是查找一个点到没到过，而是找一个中间串出没出现过，set一下就行了
#include <iostream> #include <cstring> #include <cstdlib> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <queue> #include <string> #include <map> #include <stack> #define MAXN 1000004 #define MOD 1000000009 #define INF 0x7ffffff #define lowbit(x) (x)&(-x) using namespace std; string inps; string oups; struct Node{ string s; int x,y; int step; Node(string s,int x,int y,int step):s(s),x(x),y(y),step(step){} Node(){} }; queue<Node> que; set<string> st; int dir[4][2] = {0,1,1,0,0,-1,-1,0}; inline void init(){ while(!que.empty()) que.pop(); st.clear(); } int BFS(int sx,int sy){ Node head(inps,sx,sy,0); que.push(head); st.insert(inps); string cs; while(!que.empty()){ head = que.front(); que.pop(); if(head.s == oups) return head.step; int x = head.x; int y = head.y; for(int i=0;i<4;++i){ int tx = x + dir[i][0]; int ty = y + dir[i][1]; if(tx < 0 || tx >= 3 || ty < 0 || ty >= 3) continue; cs = head.s; cs[x*3+y] = cs[tx*3+ty]; cs[tx*3+ty] = '.'; if(st.find(cs) != st.end()) continue; st.insert(cs); Node node(cs,tx,ty,head.step+1); que.push(node); } } return -1; } int main(){ while(cin >> inps >> oups){ init(); int sx,sy; for(int i=0;i<9;++i){ if(inps[i] == '.'){ sx = i/3; sy = i%3; break; } } cout << BFS(sx,sy) << endl; } return 0; }
