P2346 四子连棋【迭代加深】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int sp1x,sp1y,sp2x,sp2y;
char chess[5][5];
int cx[4]={-1,0,1,0};
int cy[4]={0,1,0,-1};
bool check(){
for(int i=1;i<=4;i++){
int j=2;
for(;j<=4;j++){
if(chess[i][j]!=chess[i][1]) break;
}
if(j==5) return 1;
}
for(int j=1;j<=4;j++){
int i=2;
for(;i<=4;i++){
if(chess[i][j]!=chess[1][j]) break;
}
if(i==5) return 1;
}
if(chess[1][1]==chess[2][2]&&chess[2][2]==chess[3][3]&&chess[3][3]==chess[4][4]) return 1;
if(chess[1][4]==chess[2][3]&&chess[2][3]==chess[3][2]&&chess[3][2]==chess[4][1]) return 1;
return 0;
}
bool ok(ll res,int s1x,int s1y,int s2x,int s2y,char now){
if(res==0) return check()?1:0;
for(int i=0;i<4;i++){
int dx=s1x+cx[i],dy=s1y+cy[i];
if(dx<=0||dx>=5||dy<=0||dy>=5||chess[dx][dy]!=now) continue;
swap(chess[dx][dy],chess[s1x][s1y]);
bool flag=ok(res-1,dx,dy,s2x,s2y,now=='B'?'W':'B');
swap(chess[dx][dy],chess[s1x][s1y]);
if(flag) return 1;
}
for(int i=0;i<4;i++){
int dx=s2x+cx[i],dy=s2y+cy[i];
if(dx<=0||dx>=5||dy<=0||dy>=5||chess[dx][dy]!=now) continue;
swap(chess[dx][dy],chess[s2x][s2y]);
bool flag=ok(res-1,s1x,s1y,dx,dy,now=='B'?'W':'B');
swap(chess[dx][dy],chess[s2x][s2y]);
if(flag) return 1;
}
return 0;
}
int main(){
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
cin>>chess[i][j];
if(chess[i][j]=='O'){
if(sp1x==0&&sp1y==0) sp1x=i,sp1y=j;
else sp2x=i,sp2y=j;
}
}
}
int lmt=0;
while(1){
if(ok(lmt,sp1x,sp1y,sp2x,sp2y,'B')){
cout<<lmt;
return 0;
}
if(ok(lmt,sp1x,sp1y,sp2x,sp2y,'W')){
cout<<lmt;
return 0;
}
lmt++;
}
return 0;
}
P2324 [SCOI2005] 骑士精神【IDA*】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
char chess[6][6];
int T,spx,spy;
int cx[8]={2,1,-1,-2,-2,-1,1,2};
int cy[8]={1,2,2,1,-1,-2,-2,-1};
char target[6][6]={
{'-','-','-','-','-','-'},
{'-','1','1','1','1','1'},
{'-','0','1','1','1','1'},
{'-','0','0','*','1','1'},
{'-','0','0','0','0','1'},
{'-','0','0','0','0','0'},
};
int check(){
int cnt=0;
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++) if(chess[i][j]!=target[i][j]) cnt++;
}
return cnt;
}
bool ok(int res,int sx,int sy){
if(res==0) return check()==0?1:0;
if(check()-1>res) return 0;
for(int i=0;i<8;i++){
int dx=sx+cx[i],dy=sy+cy[i];
if(dx<=0||dx>=6||dy<=0||dy>=6) continue;
swap(chess[dx][dy],chess[sx][sy]);
bool flag=ok(res-1,dx,dy);
swap(chess[dx][dy],chess[sx][sy]);
if(flag) return 1;
}
return 0;
}
int main(){
cin>>T;
while(T--){
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
cin>>chess[i][j];
if(chess[i][j]=='*') spx=i,spy=j;
}
}
bool flag=0;
for(int i=0;i<=15;i++){
if(ok(i,spx,spy)){
cout<<i<<endl;
flag=1;
break;
}
}
if(!flag) cout<<-1<<endl;
}
return 0;
}
P2534 [AHOI2012] 铁盘整理 【IDA*】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct plate{
int r,id;
}p[19];
int n,a[19];
bool cmp(const plate&a,const plate&b){
return a.r<b.r;
}
int check(){
int res=0;
for(int i=1;i<=n;i++) res+=(abs(a[i+1]-a[i])!=1);
return res;
}
bool ok(int lmt,int pre){
if(lmt==0) return check()==0?1:0;
if(check()>lmt) return 0;
for(int i=2;i<=n;i++){
if(i==pre) continue;
reverse(a+1,a+1+i);
bool flag=ok(lmt-1,i);
reverse(a+1,a+1+i);
if(flag) return 1;
}
return 0;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i].r;
p[i].id=i;
}
sort(p+1,p+1+n,cmp);
a[n+1]=n+1;
for(int i=1;i<=n;i++) a[p[i].id]=i;
int lmt=0;
while(1){
if(ok(lmt,-1)){
cout<<lmt;
return 0;
}
lmt++;
}
return 0;
}