「搜索」练习
2019-03-22 本文已影响0人
云中翻月
0x29「搜索」练习
2901 靶形数独
直接爆搜就是。
有两个优化：
1 每次选择可填数字最少的格子填写。
2 位运算常数优化
关于位运算，具体地说，我们将行号，列号，九宫格号从0~8编号，然后维护三个数组，保存若干个二进制数。
row[i]：表示第i行可以填写的情况，第j位若为1，就表示这一行可以填写数字j+1。
col[i]：表示第i列可以填写的情况，第j位若为1，就表示这一列可以填写数字j+1。
grid[i]：表示第i个九宫格可以填写的情况，第j位若为1，就表示这一个九宫格可以填写数字j+1。
这三个数组初始化如下
for(int i=0;i<=8;i++) row[i]=col[i]=grid[i]=(1<<9)-1;
除此之外，我们还需要维护两个数组。
cnt[i]：表示二进制数i中1的个数。
num[i]：i是2的整数次幂，表示。
这两个数组初始化如下
for(int i=0;i<=8;i++) row[i]=col[i]=grid[i]=(1<<9)-1;
for(int i=0;i<(1<<9);i++) for(int j=i;j;j-=j&-j) cnt[i]++;
内联函数g(x,y)可以求出x行y列的格子对应的九宫格编号。
inline int g(int x,int y){
return (x/3)*3+y/3;
}
flip(x,y,z)函数可以将x行y列的格子能否填写数字z+1的状态取反。
void flip(int x,int y,int z){
row[x]^=1<<z,col[y]^=1<<z,grid[g(x,y)]^=1<<z;
}
通过如下语句可以得到(i,j)这个格子能填的数字对应的二进制数。
int val=row[i]&col[j]&grid[g(i,j)];
通过如下语句可以将val里头的每一位取出来，并将其变成对应的数字z。
for(int i=val;i;i-=i&-i){
int z=num[i&-i];
//other code
}
完整代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=9+5;
const int maxm=512+5;
const int INF=0x3f3f3f3f;
const int score[maxn][maxn]={
{6,6,6,6,6,6,6,6,6},
{6,7,7,7,7,7,7,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,9,10,9,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,7,7,7,7,7,7,6},
{6,6,6,6,6,6,6,6,6}
};
int ans=0,a[maxn][maxn],row[maxn],col[maxn],grid[maxn],num[maxm],cnt[maxm],tot=0;
inline int g(int x,int y){
return (x/3)*3+y/3;
}
void flip(int x,int y,int z){
row[x]^=1<<z,col[y]^=1<<z,grid[g(x,y)]^=1<<z;
}
int cal(){
int sum=0;
for(int i=0;i<=8;i++) for(int j=0;j<=8;j++) sum+=score[i][j]*(a[i][j]+1);
return sum;
}
void dfs(int now){
if(!now){
ans=max(ans,cal());
return;
}
int temp=INF,x,y;
for(int i=0; i<=8; i++)
for(int j=0; j<=8; j++){
if(a[i][j]!=-1) continue;
int val=row[i]&col[j]&grid[g(i,j)];
if(!val) return;
if(temp>cnt[val]){
temp=cnt[val],x=i,y=j;
}
}
int val=row[x]&col[y]&grid[g(x,y)];
for(int i=val;i;i-=i&-i){
int z=num[i&-i];
flip(x,y,z);
a[x][y]=z;
dfs(now-1);
flip(x,y,z);
a[x][y]=-1;
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("靶形数独.in","r",stdin);
for(int i=0;i<=8;i++) row[i]=col[i]=grid[i]=(1<<9)-1;
for(int i=0;i<(1<<9);i++) for(int j=i;j;j-=j&-j) cnt[i]++;
for(int i=0;i<=8;i++) num[1<<i]=i;
for(int i=0; i<=8; i++)
for(int j=0; j<=8; j++) {
cin>>a[i][j];
if(a[i][j]==0) a[i][j]=-1,tot++;
else a[i][j]--,flip(i,j,a[i][j]);
}
// for(int i=0; i<=8; i++) for(int j=0; j<=8; j++) cout<<a[i][j]<<" ";
dfs(tot);
ans==0?cout<<-1:cout<<ans;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
2902 虫食算
从低位向高位依次考虑第x个字母可能放的数字。因为是n进制加法，所以每一位的数字范围为[0,n-1]。
这题实现较为繁琐，具体细节详见代码注释。
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=26+5;
const int INF=0x3f3f3f3f;
char a[maxn],b[maxn],c[maxn];
int n,f[maxn],ans[maxn],vis[maxn],d[maxn];
void init() {
for(int i=1; i<=n; i++) a[i]-='A',b[i]-='A',c[i]-='A';
for(int i=n,k=0; i>=1; i--) {
if(!vis[a[i]]) d[k++]=a[i],vis[a[i]]=1;
if(!vis[b[i]]) d[k++]=b[i],vis[b[i]]=1;
if(!vis[c[i]]) d[k++]=c[i],vis[c[i]]=1;
}
}
bool check() { //返回1表示矛盾
int p=0;//p表示进位，若为-1表示这一列三个数字中有不确定的数字
for(int i=n; i; i--) { //从低位向高位考虑
if(f[a[i]]==-1||f[b[i]]==-1||f[c[i]]==-1) p=-1;
else {
if(p==-1) { //上一位有数字不确定
if((f[a[i]]+f[b[i]])%n==f[c[i]]) { //这一位无进位
p=(f[a[i]]+f[b[i]])/n;
} else if((f[a[i]]+f[b[i]]+1)%n==f[c[i]]) { //这一位有进位
p=(f[a[i]]+f[b[i]]+1)/n;
} else return 1;
} else {
if((f[a[i]]+f[b[i]]+p)%n==f[c[i]]) {
p=(f[a[i]]+f[b[i]]+p)/n;
} else return 1;
}
}
}
return p==1; //第n+1位有进位 说明矛盾
}
bool dfs(int x) {
if(x==n) {
memcpy(ans,f,sizeof(f));
return true;
}
for(int i=n-1; i>=0; i--) { //从低位向高位考虑第x个字母可能放的数字 n进制加法 所以每一位的数字范围为[0,n-1]
f[d[x]]=i;
if(vis[i]||check()) continue;
vis[i]=1;
if(dfs(x+1)) return true;
vis[i]=0;
}
f[d[x]]=-1;
return false;
}
int main() {
// ios::sync_with_stdio(false);
//freopen("虫食算.in","r",stdin);
scanf("%d%s%s%s",&n,a+1,b+1,c+1);
init();
memset(f,-1,sizeof(f));
memset(vis, 0, sizeof(vis)); //vis数组要在这里重新初始化 用于dfs
dfs(0);
for(int i=0; i<=n-1; i++) cout<<ans[i]<<" ";
return 0;
}
#endif
2903 Mayan游戏
两个剪枝：
1 当一种颜色的方块只有1个或2个时，肯定无法消除。
2 两个方块交换时，左边的方块右移和右边的方块左移等效，所以只需考虑其中一种。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5+2;
const int maxm=7+2;
const int maxc=10+2;
const int INF=0x3f3f3f3f;
int n,a[maxn][maxm],cnt[maxc],pd[maxn][maxm];
struct node{
int x,y,g;
}ans[maxn];
void print(int b[maxn][maxm]){
for(int i=0;i<=4;i++){
for(int j=0;j<=6;j++){
cout<<b[i][j]<<" ";
}
cout<<endl;
}
}
int check(int b[maxn][maxm]){
memset(pd,0,sizeof(pd));
int flag=0;
for(int i=0;i<=4;i++)
for(int j=0;j<=6;j++){
if(b[i][j]==0) continue;
if(i<3&&b[i][j]==b[i+1][j]&&b[i+1][j]==b[i+2][j])pd[i][j]=pd[i+1][j]=pd[i+2][j]=flag=1;
//不能写成 b[i][j]==b[i+1][j]==b[i+2][j] 例如2==2==1为真
if(j<5&&b[i][j]==b[i][j+1]&&b[i][j+1]==b[i][j+2])pd[i][j]=pd[i][j+1]=pd[i][j+2]=flag=1;
}
for(int i=0;i<=4;i++)for(int j=0;j<=6;j++)if(pd[i][j])b[i][j]=0;
return flag;
}
void down(int b[maxn][maxm]){
for(int i=0;i<=4;i++){
int tot=0;
for(int j=0;j<=6;j++){
int temp=b[i][j];
b[i][j]=0;
if(temp) b[i][tot++]=temp;
}
}
}
void dfs(int step,int b[maxn][maxm]){
if(step==n){
int flag=0;
for(int i=0;i<=4;i++) for(int j=0;j<=6;j++) if(b[i][j]) flag=1;
if(!flag){
for(int i=0;i<=step-1;i++) cout<<ans[i].x<<" "<<ans[i].y<<" "<<ans[i].g<<endl;
exit(0);
}
return;
}
// print(b);
memset(cnt,0,sizeof(cnt));
for(int i=0;i<=4;i++) for(int j=0;j<=6;j++) cnt[b[i][j]]++;
for(int i=1;i<=10;i++) if(cnt[i]==1||cnt[i]==2) return; //当一种颜色的方块只有1个或2个时，肯定无法消除，所以剪枝
for(int i=0;i<=3;i++)
for(int j=0;j<=6;j++){
if(b[i][j]!=b[i+1][j]){
int temp[maxn][maxm];
memcpy(temp,b,sizeof(temp));
//这里a被当做整形 占4个字节
//而temp被作为数组 占4*6*8个字节
if(temp[i][j]){ans[step].x=i,ans[step].y=j,ans[step].g=1;}
else{ans[step].x=i+1,ans[step].y=j,ans[step].g=-1;}
swap(temp[i][j],temp[i+1][j]);
down(temp);
while(check(temp)) down(temp);
dfs(step+1,temp);
}
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Mayan游戏.in","r",stdin);
cin>>n;
for(int i=0;i<=4;i++){
int x,tot=0;
while(cin>>x&&x) a[i][tot++]=x;
}
dfs(0,a);
cout<<-1;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1167 The Buses
题意：给出n(n<=300)个数字，数字范围在[0,59]之间，要求找出最少的等差数列，不重不漏的覆盖所有数字。
method_1是自己写的IDdfs，由于每层递归时采用了枚举首项和公差的方式，所以有一个重要的可行性剪枝无法加入，最终TLE。
method_2是dfs+剪枝，预处理出m条可能的路线 ，按照覆盖的点数降序排序，因此可以做到dfs中的最优性剪枝。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
IDdfs
TLE
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=300+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],mp[maxn],sum[maxn],max_dep;
bool dfs(int dep,int now){
if(dep==0){if(now==n) return true;else return false;}
for(int i=1;i<=n;i++){ //枚举等差数列首项
if(sum[a[i]]==0||a[i]>29) continue; //车次至少两趟 所以第一班车最迟在29min到来
for(int j=1;j<=60;j++){ //枚举公差
if(a[i]+j>59||a[i]-j>=0) continue;
// if(j==25)
// cout<<"haha"<<endl;
int flag=1,cnt=0;
for(int k=0;k<=(60-a[i])/j;k++){
if(a[i]+k*j>=60) continue;
if(sum[a[i]+k*j]==0){
flag=0;
break;
}
cnt++;
}
if(flag){
for(int k=0;k<=(60-a[i])/j;k++){
if(a[i]+k*j>=60) continue;
sum[a[i]+k*j]--;
}
if(dfs(dep-1,now+cnt)){
// cout<<a[i]<<" "<<j<<" "<<cnt<<endl;
return true;
}
for(int k=0;k<=(60-a[i])/j;k++){
if(a[i]+k*j>=60) continue;
sum[a[i]+k*j]++;
}
// if(dfs(dep-1,now+cnt)) return true;
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
//freopen("The Buses.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++,sum[a[i]]++;
for(int i=1;i<=17;i++){
memcpy(sum,mp,sizeof(mp));
max_dep=i;
if(dfs(i,0)){cout<<i;break;}
}
return 0;
}
#endif
#ifdef method_2
/*
预处理出m条可能的路线
按照覆盖的点数降序排序
因此可以做到dfs中的最优性剪枝
*/
//王侯将相宁有种乎！
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1505;
int ans,cnt[60],n,m,k;
struct node {
int start,interval,times;
} r[MAXN];
bool cmp(node a,node b) {
return a.times>b.times;
}
bool pd(int time,int inter) {
while(time<60) {
if(!cnt[time]) return false;
time += inter;
}
return true;
}//判断能否成为一条公交线路；
void dfs(int k,int num,int sumr) {
//k表示目前搜到的线路， num表示当前已经有多少个记录被匹配，sumr是共用了多少个公交线路；
if(num==n) {
if(ans>sumr) ans=sumr;
return ;
}
for(int i=k; i<=m; i++) {
if(sumr + (n-num) / r[i].times >= ans) return ;//题解中说的剪枝1 最优性剪枝
if(!pd(r[i].start,r[i].interval))continue ;//题解中说的2
for( int j = r[i].start; j<60; j += r[i].interval ) {
cnt[j]--;//占用一条线路；
}
dfs(i, num + r[i].times, sumr+1);
for( int j = r[i].start; j<60; j += r[i].interval ) {
cnt[j]++;//回溯；
}
}
return ;
}
int main() {
//freopen("The Buses.in","r",stdin);
int t;
scanf("%d",&n);
memset(cnt,0,sizeof(cnt));
for(int i=1; i<=n; i++) {
scanf("%d",&t);
++cnt[t];//出现的次数；
}
m=0;
for(int i=0; i<30; i++) {
for(int j=i+1; j<60-i; j++) {
if(pd(i,j)) {
r[++m].start=i;
r[m].interval=j;
for(int l=r[m].start; l<60; l+=r[m].interval) r[m].times++;
//枚举可能的从i到j的线路；
}
}
}
sort(r+1,r+m+1,cmp);//大到小排序；
ans=17;
dfs(1,0,0);
printf("%d",ans);
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
PS：这道题上我开始IDdfs中忘记写还原现场的操作，所以写了个拍子，这里顺便附上拍子的数据生成器代码和对拍代码。
数据生成器代码
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=300+5;
const int INF=0x3f3f3f3f;
int random(int n){
return (ll)rand()*rand()%n;
}
int main() {
ios::sync_with_stdio(false);
freopen("data.in","w",stdout);
srand((unsigned)time(0));
int n=random(10)+1;
// cout<<n<<endl;
int cnt=0,a[maxn];
while(cnt<n){
int st=random(30);
int d=random(30)+1;
if(st-d>=0) continue;
int k=0;
while(st+k*d<=59) a[++cnt]=st+k*d,k++;
}
sort(a+1,a+cnt+1);
cout<<cnt<<endl;
for(int i=1;i<=cnt;i++) cout<<a[i]<<" ";
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
对拍代码
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
int main() {
ios::sync_with_stdio(false);
for(int T=1;T<=10000;T++){
system("random.exe");
double st=clock();
system("mycpp.exe");
double ed=clock();
system("std.exe");
if(system("fc mycpp.out std.out")){
puts("Wrong Answer");
system("pause");
}
else{
cout<<"Accepted"<<"测试点 "<<T<<" 用时 "<<ed-st<<" ms"<<endl;
}
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
2906 武士风度的牛
坐标变换下的最短路，用bfs即可（因为bfs第一次到达终点的时候，就得到了最优解，所以比dfs效率更优）。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=150+5;
const int INF=0x3f3f3f3f;
const int dx[]={-1,-1,-2,-2,1,1,2,2};
const int dy[]={-2,2,1,-1,-2,2,1,-1};
int n,m,vis[maxn][maxn];
char a[maxn][maxn];
struct node {
int x,y,d;
};
queue<node>q;
bool check(int x,int y){
if(x<1||x>n||y<1||y>m) return false;
return true;
}
int bfs(){
while(q.size()){
node now=q.front();q.pop();
for(int i=0;i<=7;i++){
int newx=now.x+dx[i];
int newy=now.y+dy[i];
if(!vis[newx][newy]&&check(newx,newy)){
vis[newx][newy]=1;
q.push((node){newx,newy,now.d+1});
if(a[newx][newy]=='H') return now.d+1;
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
//freopen("武士风度的牛.in","r",stdin);
cin>>m>>n;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) {
cin>>a[i][j];
if(a[i][j]=='K') q.push((node){i,j,0});
}
cout<<bfs();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
2907 乳草的入侵
类似于上一题，只不过这一次在八向联通的情况下，求最长路，仍然使用bfs即可，不过本题需要特别注意题目中行列的含义。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n,m,mx,my,d[maxn][maxn];
char a[maxn][maxn];
struct node{
int x,y,d;
};
queue<node>q;
bool check(int x,int y){
if(x<1||x>n||y<1||y>m) return false;
return true;
}
int bfs(){
int ans=-1;
while(q.size()){
node now=q.front();q.pop();
for(int i=-1;i<=1;i++) for(int j=-1;j<=1;j++){
int newx=now.x+i,newy=now.y+j;
if(check(newx,newy)&&d[newx][newy]==-1&&a[newx][newy]!='*'){
ans=max(ans,now.d+1);
d[newx][newy]=now.d+1;
q.push((node){newx,newy,now.d+1});
}
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
//freopen("乳草的入侵.in","r",stdin);
memset(d,-1,sizeof(d));
cin>>m>>n>>my>>mx;mx=n-mx+1; //这里行列杀我
q.push((node){mx,my,0}),d[mx][my]=0;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
cout<<bfs()<<endl;
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<d[i][j]<<" ";
}
cout<<endl;
}
*/
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
2908 字串变换
考虑到变换规则可逆，起始状态和最终状态都确定，每一层搜索树分支较多，搜索树的最深层数不超过10，这四个特征，我们可以使用双向BFS求解。
代码如下
/*
双向BFS：
1.正向搜索：从初始结点向目标结点方向搜索，按照正向规则(A$->B$)变换。
2.逆向搜索：从目标结点向初始结点方向搜索，按照逆向规则(B$->A$)变换。
当两个方向的搜索生成同一子结点时终止此搜索过程(变换的总步数为此时两个方向BFS的步数总和)。
双向搜索通常有两种方法：
1. 两个方向交替扩展。
2. 选择结点个数较少的那个方向先扩展。
方法2克服了两方向结点的生成速度不平衡的状态,明显提高了效率。本程序使用方法1，两个方向交替BFS，进行正反规则变换。
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
struct Node {
char str[41];
int sep;
Node() {
sep=0;
// memset(str,sizeof(str),0);
}
} q1[20000], q2[20000];
int h1, r1, h2, r2; //h1,r1...h2,r2,分别保存起始和目标两个状态的队列头和尾
char s1[6][25], s2[6][25]; //存储变换规则
int n,Min=100; //Min储存最少规则变换次数
void copy2(int start, int use) { //逆向搜索，当q2[]搜索到逆向规则匹配的字串B$的时候，进行替换
int i, j;
r2++; //队列中元素增加1个字串
q2[r2].sep = q2[h2].sep + 1;
for(i = 0; i < start; i++) { //替换匹配规则的字串
q2[r2].str[i] = q2[h2].str[i];
}
for(j = 0; s1[use][j] != '\0'; j++, i++) {
q2[r2].str[i] = s1[use][j];
}
for(j = start + strlen(s2[use]); q2[h2].str[j] != '\0'; j++, i++) {
q2[r2].str[i] = q2[h2].str[j];
}
//cout<<"q2:"<<q2[r2].str<<endl;
for(i = 0; i <= r1; i++) { //判断这一次规则替换操作结束后，正向BFS队列中是否会有字串元素与之匹配
if(strcmp(q1[i].str, q2[r2].str) == 0) {
printf("%d\n", q1[i].sep + q2[r2].sep);
exit(0);
// if(q1[i].sep+q2[r2].sep<Min) Min=q1[i].sep+q2[r2].sep;
}
}
}
void copy1(int start, int use) { //正向搜索，当q1[]搜索到与规则匹配的字串A$的时候，进行替换
int i, j;
r1++;
q1[r1].sep = q1[h1].sep + 1; //队列q1[]中增加1个新的元素(一次规则变换后的字串)
for(i = 0; i < start; i++) { //规则替换操作
q1[r1].str[i] = q1[h1].str[i];
}
for(j = 0; s2[use][j] != '\0'; j++, i++) {
q1[r1].str[i] = s2[use][j];
}
for(j = start + strlen(s1[use]); q1[h1].str[j] != '\0'; j++, i++) {
q1[r1].str[i] = q1[h1].str[j];
}
//cout<<"q1:"<<q1[r1].str<<endl;
for(i = 0; i <= r2; i++) { //判断这一次规则替换操作结束后，方向BFS队列中是否会有字串元素与之匹配
if(strcmp(q2[i].str, q1[r1].str) == 0) {
printf("%d\n", q2[i].sep + q1[r1].sep);
exit(0);
// if(q2[i].sep+q1[r1].sep<Min) Min=q2[i].sep+q1[r1].sep;
}
}
}
void work(void) {
int i, j;
while(h1 <= r1 && h2 <= r2) { //搜索过程中确保没有一个队列为空，否则搜索不到相交的情况
if(q1[h1].sep + q2[h2].sep > 10) { //正反搜索的步数总和超过了10，说明这样的转换至少要超过10次才能实现，结束
printf("NO ANSWER!\n");
exit(0);
}
for(i = 0; i < strlen(q1[h1].str); i++) {
for(j = 0; j < n; j++) { //正向搜索，一共n个变换规则
if(strncmp(s1[j], &q1[h1].str[i], strlen(s1[j])) == 0) { // 从q1[h1].str[i]开始的位置比较 比较长度为strlen(s1[j])
copy1(i, j);
}
}
}
h1++; //正向一遍BFS，搜索完所有规则之后，队首元素出队
for(i = 0; i < strlen(q2[h2].str); i++) { //加快搜索的速度，同理从目标开始，方向，并根据逆向规则进行BFS
for(j = 0; j < n; j++) {
if(strncmp(s2[j], &q2[h2].str[i], strlen(s2[j])) == 0) {
copy2(i, j);
}
}
}
h2++;
}
}
int main() {
//freopen("字串变换.in","r",stdin);
scanf("%s%s", q1[0].str, q2[0].str);
while(scanf("%s%s", s1[n], s2[n]) == 2) {
n++;
}
work();
printf("NO ANSWER!\n");
return 0;
}
POJ2044 Weather Forecast
由于四个角(1,1)(1,4)(4,1)(4,4)最难以照顾 所以判断是否有城市连续7天不下雨只需判断4个角即可。
有了这个大优化，我们就能够在空间允许的范围内表示状态了。
struct node{
int x,y,d,s1,s2,s3,s4;//云层左上角在(x,y) 当前为第d天 (1,1)(1,4)(4,1)(4,4)没有下雨的天数分别为s1,s2,s3,s4
};
另外，为了记忆化状态，我们采用vis[a,b,c,d,e,f,g,h]表示第c天 云层左上角在(a,b)时 (1,1)(1,4)(4,1)(4,4)没有下雨的天数分别为e,f,g,h的状态是否到达过。
PS：这道题目bfs写法不能全部AC，即代码中method_1是TLE版本，method_2用dfs可以AC。
代码如下
/*
method_1用bfs TLE
method_2用dfs 340msAC
*/
#define method_1
#ifdef method_1
/*
由于四个角(1,1)(1,4)(4,1)(4,4)最难以照顾 所以判断是否有城市连续7天不下雨只需判断4个角即可
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=366+5;
const int maxp=5+1;
const int maxd=7+1;
const int INF=0x3f3f3f3f;
const int dx[]={0,1,-1,2,-2,0,0,0,0};
const int dy[]={0,0,0,0,0,1,-1,2,-2};
struct node{
int x,y,d,s1,s2,s3,s4;//云层左上角在(x,y) 当前为第d天 (1,1)(1,4)(4,1)(4,4)没有下雨的天数分别为s1,s2,s3,s4
};
queue<node>q;
int n,a[maxn][maxp][maxp],vis[maxp][maxp][maxn][maxd][maxd][maxd][maxd];
//vis[a,b,c,d,e,f,g,h]表示第c天 云层左上角在(a,b)时 (1,1)(1,4)(4,1)(4,4)没有下雨的天数分别为e,f,g,h的状态是否到达过
inline bool check(int x,int y,int d,int s1,int s2,int s3,int s4){
if(x<1||x>3||y<1||y>3) return false;
if(a[d][x][y]||a[d][x+1][y]||a[d][x][y+1]||a[d][x+1][y+1]) return false;
if(s1>=7||s2>=7||s3>=7||s4>=7) return false;
return true;
}
inline bool bfs(){
while(q.size()) q.pop();
q.push((node){2,2,1,1,1,1,1});
memset(vis,0,sizeof(vis));//多组数据 这里要初始化
vis[2][2][1][1][1][1][1]=1;
if(a[1][2][2]||a[1][2][3]||a[1][3][2]||a[1][3][3]) return false;
while(q.size()){
node now=q.front();q.pop();
if(now.d==n) return true;
for(int i=0;i<=8;i++){
int newx=now.x+dx[i],newy=now.y+dy[i];
int s1=now.s1+1,s2=now.s2+1,s3=now.s3+1,s4=now.s4+1;
if(newx==1&&newy==1) s1=0;
if(newx==1&&newy==3) s2=0;
if(newx==3&&newy==1) s3=0;
if(newx==3&&newy==3) s4=0;
if(check(newx,newy,now.d+1,s1,s2,s3,s4)&&!vis[newx][newy][now.d+1][s1][s2][s3][s4]){
vis[newx][newy][now.d+1][s1][s2][s3][s4]=1;
q.push((node){newx,newy,now.d+1,s1,s2,s3,s4});
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Weather Forecast.in","r",stdin);
while(cin>>n&&n){
for(int i=1;i<=n;i++) for(int j=1;j<=4;j++) for(int k=1;k<=4;k++) cin>>a[i][j][k];
bfs()?cout<<1<<endl:cout<<0<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int n;
int dir[9][2] = {{0, 0}, {-1, 0}, {-2, 0}, {0, -1}, {0, -2}, {1, 0}, {2, 0}, {0, 1}, {0, 2}};
int days[377];
int vis[377][9][7][7][7][7];
bool check(int day, int x, int y, int d1, int d2, int d3, int d4) {
if (d1 == 7 || d2 == 7 || d3 == 7 || d4 == 7 || vis[day][3 * x + y][d1][d2][d3][d4]) return false;
if(((1 << (4 * x + y))
| (1 << (4 * x + y + 1))
| (1 << (4 * (x + 1) + y))
| (1 << (4 * (x + 1) + y + 1)))
& days[day]) return false;
return true;
}
bool dfs(int day, int x, int y, int d1, int d2, int d3, int d4) {
if (day == n) return true;
int n1 = d1, n2 = d2, n3 = d3, n4 = d4;
n1++;
if (x == 0 && y == 0) n1 = 0;
n2++;
if (x == 0 && y == 2) n2 = 0;
n3++;
if (x == 2 && y == 0) n3 = 0;
n4++;
if (x == 2 && y == 2) n4 = 0;
if (!check(day, x, y, n1, n2, n3, n4)) return false;
vis[day][3 * x + y][n1][n2][n3][n4] = 1;
for (int i = 0; i < 9; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
if (dfs(day + 1, nx, ny, n1, n2, n3, n4)) return true;
}
}
return false;
}
int main() {
while (~scanf("%d", &n) && n) {
memset(days, 0, sizeof(days));
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; i++) {
int t;
for (int j = 0; j < 16; j++) {
scanf("%d", &t);
days[i] <<= 1;
days[i] |= t;
}
}
int ans = dfs(0, 1, 1, 0, 0, 0, 0);
cout << ans << endl;
}
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
POJ1945 Power Hungry Cows
首先考虑表示状态，每个状态包括一个数组，即达到当前值中途所产生的所有值。但是这样数组过大，所以会选择只用一个二元组(a,b)表示目前这一次操作用到了两个值。为了避免(a,b)和(b,a)表示重复，所以我们令。
但是这样状态依然很多，所以我们采用启发式bfs，即算法。估价函数为把a不断自加直至>=n所需的次数（注意a>=b），显然实际所需次数不会小于这一次数。
因此最终的状态为一个四元组(a,b,val,cnt)。未来估价val，当前次数cnt。并将四元组存入优先队列，按照cnt+val升序排序。
同样我们采用链式前向星（手写hash）对状态判重。hash函数为，并取模。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000000+5;
const int INF=32768;
const int mod=999983;
int n,d[maxn],tot=1,head[maxn];
struct node{
int a,b,val,cnt;
};
bool operator<(const node &x,const node &y){
return x.val+x.cnt>y.val+y.cnt;
}
struct node1{
int from;
pii to;
}edge[maxn];
priority_queue<node>q;
int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
int cal(int a){
int val=0;
for(;a<n;a<<=1)val++;
return val;
}
bool update(int a,int b,int cnt){
int ha=a*b%mod;
for(int i=head[ha];i;i=edge[i].from){
if(edge[i].to.first==a&&edge[i].to.second==b){
if(d[i]>cnt){
d[i]=cnt;
return true;
}
return false;
}
}
d[++tot]=cnt;
edge[tot].to.first=a,edge[tot].to.second=b;
edge[tot].from=head[ha],head[ha]=tot;
return true;
}
void insert(int a,int b,int cnt){
if(a<b) swap(a,b);
if(a>INF||b>INF) return;
if(n%gcd(a,b)) return;
bool f=update(a,b,cnt);
if(f) q.push((node){a,b,cal(a),cnt});
}
int astar(){
insert(1,0,0);
while(q.size()){
node now=q.top();q.pop();
if(now.a==n||now.b==n) return now.cnt;
insert(now.a*2,now.b,now.cnt+1);
insert(now.a,now.b*2,now.cnt+1);
if(now.a) insert(now.a*2,now.a,now.cnt+1);
if(now.b) insert(now.b*2,now.b,now.cnt+1);
if(now.a-now.b>=0){
insert(now.a-now.b,now.a,now.cnt+1),insert(now.a-now.b,now.b,now.cnt+1);
}
if(now.b-now.a>=0){
insert(now.b-now.a,now.a,now.cnt+1),insert(now.b-now.a,now.b,now.cnt+1);
}
insert(now.a+now.b,now.a,now.cnt+1),insert(now.a+now.b,now.b,now.cnt+1);
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Power Hungry Cows.in","r",stdin);
cin>>n;
cout<<astar();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
2912 Flood-it!
看到一个较为复杂状态的dfs求最优解，想到迭代加深搜索。
看到局面可以估价，想到启发式搜索。
因此可以使用IDA-dfs。
考虑估价函数f()的设计。
int f() { //估价函数 求a数组中除了(1,1)所在联通块的颜色，总共有sum种不同颜色
int sum=0;
memset(cnt,0,sizeof(cnt));
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(vis[i][j]!=1&&!cnt[a[i][j]]) {
cnt[a[i][j]]=1,sum++;
}
return sum;
}
但是这样直接加上dfs/bfs灌水，依然无法ac，因此我们需要考虑增加其他优化。
优化1 每次朝着(1,1)所在联通块变大的方向搜索。
优化2 每次已经灌水过的部分不再理会，只朝着没有灌水过的部分推进 。
代码如下（其中method_1为不加如上两个优化的版本，50分，剩余部分TLE，method_2为100分）
/*
*/
#define method_2
#ifdef method_1
/*
先用了dfs来灌水，后来超时50分，又改成了用bfs灌水，还是TLE
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=8+2;
const int INF=0x3f3f3f3f;
const int dx[]= {1,-1,0,0};
const int dy[]= {0,0,1,-1};
int n,a[maxn][maxn],cnt[maxn],dep,vis[maxn][maxn];
queue<pii>q;
int f(int a[maxn][maxn]) { //估价函数 求a数组中总共有sum种不同颜色
int sum=0;
memset(cnt,0,sizeof(cnt));
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cnt[a[i][j]]++;
for(int i=0; i<=5; i++) if(cnt[i]) sum++;
return sum;
}
bool check(int x,int y) {
if(x<1||x>n||y<1||y>n) return false;
return true;
}
void show(int b[maxn][maxn]) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
cout<<b[i][j];
}
cout<<endl;
}
cout<<endl;
}
void bfs(int x,int y,int b[maxn][maxn],int c1,int c2) {
//从(x,y)开始染色，将b数组中原本c1的颜色 染成c2
// show(b);
while(q.size()) q.pop();
q.push(make_pair(x,y));
// memset(vis,0,sizeof(vis));
vis[x][y]=1;
while(q.size()) {
pii p=q.front();
q.pop();
b[p.first][p.second]=c2;
for(int i=0; i<=3; i++) {
int newx=p.first+dx[i],newy=p.second+dy[i];
if(check(newx,newy)&&b[newx][newy]==c1&&!vis[newx][newy]) {
vis[newx][newy]=1,q.push(make_pair(newx,newy));
}
}
}
// show(b);
}
int v[maxn][maxn];
void change(int x,int y,int c1,int c2) {
//从(x,y)开始染色，将v数组中原本c1的颜色 染成c2
v[x][y]=c2;
vis[x][y]=1;
for(int i=0; i<=3; i++) {
int newx=x+dx[i],newy=y+dy[i];
if(check(newx,newy)&&v[newx][newy]==c1&&!vis[newx][newy]) {
vis[newx][newy]=1,change(newx,newy,c1,c2);
}
}
}
bool dfs(int d,int a[maxn][maxn]) {
// show(a);
if(f(a)==1) return true;
if(d+f(a)-1>dep) return false; //估价函数 如果还有f(a)种颜色 只要要f(a)-1次操作
int b[maxn][maxn];
for(int i=0; i<=5; i++) {
if(cnt[i]) { //剪枝1 只转化为棋盘上已有的颜色
memcpy(v,a,sizeof(v));
memset(vis,0,sizeof(vis));
change(1,1,a[1][1],i);
memcpy(b,v,sizeof(b));
//----------------
//bfs(1,1,b,a[1][1],i);
//----------------
if(dfs(d+1,b)) {
// show(b);
return true;
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Flood-it!.in","r",stdin);
while(cin>>n&&n) {
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin>>a[i][j];
for(dep=0; dep<=64; dep++) {
if(dfs(0,a)) {
cout<<dep<<endl;
break;
}
}
}
return 0;
}
#endif
#ifdef method_2
/*
通过对vis数组的改进，加入了两个优化，ac
优化1 每次朝着(1,1)所在联通块变大的方向搜索
优化2 每次已经灌水过的部分不再理会 只朝着没有灌水过的部分推进
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=8+2;
const int INF=0x3f3f3f3f;
const int dx[]= {1,-1,0,0};
const int dy[]= {0,0,1,-1};
int n,a[maxn][maxn],cnt[maxn],dep,vis[maxn][maxn];
//vis[i,j]=1表示(i,j)已经处于联通块中， vis[i,j]=2表示(i,j)和(1,1)所在联通块直接相邻且颜色不同
int f() { //估价函数 求a数组中除了(1,1)所在联通块的颜色，总共有sum种不同颜色
int sum=0;
memset(cnt,0,sizeof(cnt));
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(vis[i][j]!=1&&!cnt[a[i][j]]) {
cnt[a[i][j]]=1,sum++;
}
return sum;
}
bool check(int x,int y) {
if(x<1||x>n||y<1||y>n) return false;
return true;
}
void show(int b[maxn][maxn]) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
cout<<b[i][j];
}
cout<<endl;
}
cout<<endl;
}
void change(int x,int y,int c2) {
//从(x,y)开始染色
vis[x][y]=1;
for(int i=0; i<=3; i++) {
int newx=x+dx[i],newy=y+dy[i];
if(check(newx,newy)&&vis[newx][newy]!=1) { //优化2 每次已经灌水过的部分不再理会
vis[newx][newy]=2;
if(a[newx][newy]==c2)change(newx,newy,c2);
}
}
}
bool dfs(int d) {
// show(a);
int gj=f();
if(gj==0) return true;
if(d+gj>dep) return false; //估价函数 如果除了(1,1)所在联通块的颜色还有f(a)种颜色 只要f(a)操作
int b[maxn][maxn];
memcpy(b,vis,sizeof(b));
for(int i=0; i<=5; i++) {
bool flag=0;
for(int j=1; j<=n; j++) for(int k=1; k<=n; k++) {
if(a[j][k]==i&&vis[j][k]==2){ //将(1,1)所在联通块的颜色变成i 并用change扩展联通块
flag=1,change(j,k,i);
}
}
if(flag&&dfs(d+1)) { //flag=1表示(1,1)所在联通块在增大 如果没有增大，则剪枝（优化1）
// show(b);
return true;
}
memcpy(vis,b,sizeof(vis)); //回溯
}
return false;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Flood-it!.in","r",stdin);
while(cin>>n&&n) {
memset(vis,0,sizeof(vis));
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin>>a[i][j];
change(1,1,a[1][1]);
// show(vis);
for(dep=0; dep<=64; dep++) {
if(dfs(0)) {
cout<<dep<<endl;
break;
}
}
}
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
