对（1）的拓展，加个结构体保存路径
https://blog.csdn.net/qq_37591656/article/details/80014307
poj炸了不知道能否AC
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>using namespace std;
typedef long long int ll;const int maxn=(1<<16)-1;
const int inf=0x3f3f3f3f;queue<int> que;
int vis[maxn+10];
int step;int endk;struct Father{int lastState;int p;
}father[maxn+10];int change(unsigned int x,int i,int j)
{int k;k=(1<<(i*4+j));x^=k;int t = i-1;while(t>=0){k=(1<<(4*t--+j));x^=k;}t = i+1;while(t<4){k=(1<<(4*(t++)+j));x^=k;}t = j+1;while(t<4){k=(1<<(4*i+t++));x^=k;}t = j-1;while(t>=0){k=(1<<(4*i+t--));x^=k;}return x;
}int bfs(int state)
{step=0;while(!que.empty())que.pop();que.push(state);while(!que.empty()){int t=que.size();for(int i=0; i<t; i++){int k=que.front();que.pop();if(k==0||k==maxn||step>16){endk = k;return step;}for(int p=0; p<4; p++)for(int q=0; q<4; q++){int w;w=change(k,p,q);if(!vis[w]){que.push(w);father[w].p = p*4+q;father[w].lastState = k;}vis[w]=1;}}step++;}
}int main()
{int state=0;char s[10];int k=0;for(int i=0; i<4; i++){scanf("%s",s);for(int j=0; j<4; j++){if(s[j]=='-')state+=(1<<k);k++;}}father[state].p = -1;int ans=bfs(state);printf("%d\n",ans);while(endk != state){int t = father[endk].p;cout<<t/4 +1 <<' '<<t%4 +1<<endl;endk = father[endk].lastState;}return 0;
}