备战蓝桥杯---搜索（应用入门）

话不多说，直接看题：

显然，我们可以用BFS，其中，对于判重操作，我们可以把这矩阵化成字符串的形式再用map去存，用a数组去重现字符串（相当于map映射的反向操作）。移动空格先找到x的位置再推算出在矩阵里的位置进行移动即可。

至于如何回溯，我们创造last数组来看它上一个是谁，用form数组记录变化的操作。

然后dfs回溯输出即可。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
#define N 363000
int last[N],cnt;
int form[N];
char dd;
map<string,int> mp;
string a[N],s1,s2="12345678x";
queue<int> 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;cnt=1;last[cnt]=0;a[cnt]=s1;q.push(cnt);while(!q.empty()){int tmp=q.front();q.pop();int tt=a[tmp].find('x');int x=tt/3,y=tt%3;for(int i=0;i<4;i++){string nxt=a[tmp];int x1=x+dir[i][0];int y1=y+dir[i][1];if(x1<0||x1>=3||y1<0||y1>=3) continue;swap(nxt[tt],nxt[x1*3+y1]);if(mp.find(nxt)!=mp.end()) continue;mp[nxt]=++cnt;last[cnt]=tmp;form[cnt]=i;a[cnt]=nxt;q.push(cnt);if(nxt==s2) return 1;}}return 0;
}
void dfs(int cnt){if(cnt==1) return;dfs(last[cnt]);cout<<ck[form[cnt]];
}
int main(){for(int i=1;i<=9;i++){cin>>dd;s1+=dd;}if(bfs(s1,s2)==0) cout<<"unsolvable";else dfs(mp[s2]);
}

注意：方向数组中（1，0）是down（因为这wa了好久）

下面来一道刚刚比赛过的题：

这名字显然是个坑，看到数据范围就知道要暴力了3^10是可以接受的，于是我们用dfs写

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,t,a[20],min1=20;
struct node{int u,v;
}q[20];
void deal(){int cnt=1;for(int i=2;i<=n;i++){if(a[i]>a[1]) cnt++;}min1=min(min1,cnt);
}
void dfs(int x){if(x>m){deal();return ;}for(int i=1;i<=3;i++){if(i==1){a[q[x].u]+=3;dfs(x+1);a[q[x].u]-=3;}else if(i==2){a[q[x].v]+=3;dfs(x+1);a[q[x].v]-=3;}else{a[q[x].u]+=1;a[q[x].v]+=1;dfs(x+1);a[q[x].u]-=1;a[q[x].v]-=1;}}return ;
}
int main(){cin>>t;while(t--){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>q[i].u>>q[i].v;dfs(1);cout<<min1<<endl;min1=20;}
}