天津网站seo策划,锦州网站设计,app网站与普通网站的区别,培训心得体会感悟话不多说#xff0c;直接看题#xff1a; 显然#xff0c;我们可以用BFS#xff0c;其中#xff0c;对于判重操作#xff0c;我们可以把这矩阵化成字符串的形式再用map去存#xff0c;用a数组去重现字符串#xff08;相当于map映射的反向操作#xff09;。移动空格先找…话不多说直接看题 显然我们可以用BFS其中对于判重操作我们可以把这矩阵化成字符串的形式再用map去存用a数组去重现字符串相当于map映射的反向操作。移动空格先找到x的位置再推算出在矩阵里的位置进行移动即可。
至于如何回溯我们创造last数组来看它上一个是谁用form数组记录变化的操作。
然后dfs回溯输出即可。
下面是AC代码
#includebits/stdc.h
using namespace std;
#define N 363000
int last[N],cnt;
int form[N];
char dd;
mapstring,int mp;
string a[N],s1,s212345678x;
queueint q;
int dir[4][2]{{0,1},{0,-1},{-1,0},{1,0}};
char ck[4]{r,l,u,d};
int bfs(string s1,string s2){mp[s1]1;cnt1;last[cnt]0;a[cnt]s1;q.push(cnt);while(!q.empty()){int tmpq.front();q.pop();int tta[tmp].find(x);int xtt/3,ytt%3;for(int i0;i4;i){string nxta[tmp];int x1xdir[i][0];int y1ydir[i][1];if(x10||x13||y10||y13) continue;swap(nxt[tt],nxt[x1*3y1]);if(mp.find(nxt)!mp.end()) continue;mp[nxt]cnt;last[cnt]tmp;form[cnt]i;a[cnt]nxt;q.push(cnt);if(nxts2) return 1;}}return 0;
}
void dfs(int cnt){if(cnt1) return;dfs(last[cnt]);coutck[form[cnt]];
}
int main(){for(int i1;i9;i){cindd;s1dd;}if(bfs(s1,s2)0) coutunsolvable;else dfs(mp[s2]);
}
注意方向数组中10是down因为这wa了好久
下面来一道刚刚比赛过的题 这名字显然是个坑看到数据范围就知道要暴力了3^10是可以接受的于是我们用dfs写
下面是AC代码
#includebits/stdc.h
using namespace std;
int n,m,t,a[20],min120;
struct node{int u,v;
}q[20];
void deal(){int cnt1;for(int i2;in;i){if(a[i]a[1]) cnt;}min1min(min1,cnt);
}
void dfs(int x){if(xm){deal();return ;}for(int i1;i3;i){if(i1){a[q[x].u]3;dfs(x1);a[q[x].u]-3;}else if(i2){a[q[x].v]3;dfs(x1);a[q[x].v]-3;}else{a[q[x].u]1;a[q[x].v]1;dfs(x1);a[q[x].u]-1;a[q[x].v]-1;}}return ;
}
int main(){cint;while(t--){cinnm;for(int i1;in;i) cina[i];for(int i1;im;i) cinq[i].uq[i].v;dfs(1);coutmin1endl;min120;}
}
