双向BFS:
分别在 起点 和 终点同时进行BFS。
一般地,BFS随着层数的增加,状态数会越来越多,也就是状态数与层数呈正相关。如下图,:
若从两端同时进行BFS ,则有
显然减少的哪一些区域即为减掉的那些不必要的状态。
#include <iostream> #include <algorithm> #include <cstdlib> #include <cstdio> #include <cstring> #include <queue> #include <cmath> #include <stack> #include <map> #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long LL #define _LL __int64 #define _INF 0x3f3f3f3f #define Mod 1000000007 #define LM(a,b) (((ULL)(a))<<(b)) #define RM(a,b) (((ULL)(a))>>(b)) using namespace std; struct N { int a[4]; int ans,ty; }; int mark[10][10][10][10][2]; void bfs(N s,N e) { queue<N> q; s.ans = 0; s.ty = 0; e.ans = 0; e.ty = 1; memset(mark,-1,sizeof(mark)); q.push(s); q.push(e); mark[s.a[0]][s.a[1]][s.a[2]][s.a[3]][s.ty] = 0; mark[e.a[0]][e.a[1]][e.a[2]][e.a[3]][e.ty] = 0; N f,t; while(q.empty() == false) { f = q.front(); q.pop(); if(mark[f.a[0]][f.a[1]][f.a[2]][f.a[3]][!f.ty] != -1) { printf("%d\n",f.ans + mark[f.a[0]][f.a[1]][f.a[2]][f.a[3]][!f.ty]); return; } for(int i = 0;i < 3; ++i) { for(int j = 0;j < 4; ++j) { if(i == j) { t.a[i] = f.a[i+1]; } else if(i == j-1) { t.a[i+1] = f.a[i]; } else t.a[j] = f.a[j]; } t.ans = f.ans+1; t.ty = f.ty; if(mark[t.a[0]][t.a[1]][t.a[2]][t.a[3]][t.ty] == -1) { mark[t.a[0]][t.a[1]][t.a[2]][t.a[3]][t.ty] = t.ans; q.push(t); } } for(int i = 0;i < 4; ++i) { for(int j = 0;j < 4; ++j) { if(i == j) { t.a[i] = f.a[i]+1; if(t.a[i] == 10) t.a[i] = 1; } else t.a[j] = f.a[j]; } t.ans = f.ans+1; t.ty = f.ty; if(mark[t.a[0]][t.a[1]][t.a[2]][t.a[3]][t.ty] == -1) { mark[t.a[0]][t.a[1]][t.a[2]][t.a[3]][t.ty] = t.ans; q.push(t); } } for(int i = 0;i < 4; ++i) { for(int j = 0;j < 4; ++j) { if(i == j) { t.a[i] = f.a[i]-1; if(t.a[i] == 0) t.a[i] = 9; } else t.a[j] = f.a[j]; } t.ans = f.ans+1; t.ty = f.ty; if(mark[t.a[0]][t.a[1]][t.a[2]][t.a[3]][t.ty] == -1) { mark[t.a[0]][t.a[1]][t.a[2]][t.a[3]][t.ty] = t.ans; q.push(t); } } } } int main() { N s,e; int T; scanf("%d",&T); while(T--) { for(int i = 0;i < 4; ++i) scanf("%1d",&s.a[i]); for(int i = 0;i < 4; ++i) scanf("%1d",&e.a[i]); bfs(s,e); } return 0; }
原文:http://blog.csdn.net/zkn_cs_dn_2013/article/details/25296535