分析：很显然这是一道搜索题，可能是由于我的搜索打的太不美观了，这道题又WA又T......如果对每一个询问都做一次bfs是肯定会T的，注意到前70%的数据范围，N的值都相等，我们可以把给定N的所有情况给算出来，然后O（1）查询.从终点状态往起点状态BFS就可以了.
当最终状态很少，起始状态很多的时候，可以考虑倒着做.
#include#include #include #include #include using namespace std;int T, jian[10], stu, shu[10], cnt, top[10], d[10000000], cur[10], vis[10000000];int n, a[10], b[10];queue q;bool cmp(int x, int y){ return a[x] < a[y];}void bfs(){ while (!q.empty()) { int zhuangtai = q.front(); q.pop(); memset(top, 0, sizeof(top)); memset(shu, 0, sizeof(shu)); cnt = 0; int tt = zhuangtai; while (tt) { shu[++cnt] = tt % 10; tt /= 10; } reverse(shu + 1, shu + 1 + cnt); for (int i = cnt; i >= 1; i--) top[shu[i]] = i; for (int i = 1; i <= cnt; i++) if (i == top[shu[i]]) { int temp = shu[i]; if (temp != 1 && (i < top[temp - 1] || !top[temp - 1])) { int newstu = zhuangtai - jian[cnt - i]; if (!vis[newstu]) { q.push(newstu); vis[newstu] = 1; d[newstu] = d[zhuangtai] + 1; } } if (temp != cnt && (i < top[temp + 1] || !top[temp + 1])) { int newstu = zhuangtai + jian[cnt - i]; if (!vis[newstu]) { q.push(newstu); vis[newstu] = 1; d[newstu] = d[zhuangtai] + 1; } } } }}int main(){ scanf("%d", &T); jian[0] = 1; stu = 0; for (int i = 1; i <= 7; i++) { jian[i] = jian[i - 1] * 10; stu = stu * 10 + i; q.push(stu); vis[stu] = 1; } bfs(); //printf("flag\n"); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = i; } sort(b + 1, b + 1 + n, cmp); int stu = 0; for (int i = 1; i <= n; i++) stu = stu * 10 + b[i]; if (!vis[stu]) printf("-1\n"); else printf("%d\n", d[stu]); } return 0;}