這個(gè)搜索題折騰了我不少時(shí)間，代碼跑得比較慢 效率還有提升的空間
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
struct node
{
int x1,y1;
int x2,y2;
int time;
}l[10000000];
int v[50][50][50][50];
int m[100][100];
void myswap(int &x,int &y)
{
int t=x;
x=y;
y=t;
}
int hx1,hy1;
int hx2,hy2;
char str[100];
int n,mm;//n為高m為寬
void input(int n,int mm)
{
int cnt=1;
int cnt2=1;
int i,j;
int len;
for(i=0;i<n;i++)
{
scanf("%s",str);
len=strlen(str);
for(j=0;j<len;j++)
{
if(str[j]=='*')
m[i][j]=2;
else if(str[j]=='B')
{
m[i][j]=0;
if(cnt==1)
{
l[1].x1=i;
l[1].y1=j;
cnt++;
}
else if(cnt==2)
{
l[1].x2=i;
l[1].y2=j;
}
}
else if(str[j]=='H')
{
m[i][j]=-1;
if(cnt2==1)
{
hx1=i;
hy1=j;
cnt2++;
}
else if(cnt2==2)
{
hx2=i;
hy2=j;
}
}
else if(str[j]=='.')
m[i][j]=0;
}
}
}
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1} };
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int i;
memset(v,false,sizeof(v));
scanf("%d%d",&n,&mm);
input(n,mm);
v[l[1].x1][l[1].y1][l[1].x2][l[1].y2]=true;
l[1].time=0;
int front,rear;
front=rear=1;
while(front<=rear)
{
if(m[l[front].x1][l[front].y1]==-1&&m[l[front].x2][l[front].y2]==-1&&(l[front].x1!=l[front].x2||l[front].y1!=l[front].y2))
break;
for(i=0;i<4;i++)
{
int tx1=l[front].x1;
int ty1=l[front].y1;
int tx2=l[front].x2;
int ty2=l[front].y2;
int tt=l[front].time;//存下步數(shù)
if(i==0)
{
if(tx1>tx2)
{
myswap(tx1,tx2);
myswap(ty1,ty2);
}
}
else if(i==1)
{
if(ty1<ty2)
{
myswap(tx1,tx2);
myswap(ty1,ty2);
}
}
else if(i==2)
if(tx1<tx2)
{myswap(tx1,tx2); myswap(ty1,ty2);}
else if(i==3)
{
if(ty1>ty2)
{
myswap(tx1,tx2);
myswap(ty1,ty2);
}
}
if(m[tx1][ty1]==-1&&(tx1!=tx2||ty1!=ty2) )
goto next1;
if(m[tx1][ty1]==-1&&tx1==tx2&&ty1==ty2&&m[tx1+dir[i][0]][ty1+dir[i][1]]==-1<2)
{
tx1+=dir[i][0];
ty1+=dir[i][1];
}
else if(m[tx1+dir[i][0]][ty1+dir[i][1]]==-1)//下一個(gè)位置是洞，且洞中無球
{
// m[tx1+dir[i][0]][ty1+dir[i][1]]=0;
// m[tx1][ty1]=0;
tx1+=dir[i][0];
ty1+=dir[i][1];
}
else if(m[tx1+dir[i][0]][ty1+dir[i][1]]==0)
{
// m[tx1+dir[i][0]][ty1+dir[i][1]]=1;
// m[tx2][ty2]=0;
tx1+=dir[i][0];
ty1+=dir[i][1];
}
next1: //第二個(gè)球運(yùn)動(dòng)
if(m[tx2][ty2]==-1)
goto next2;
else if(tx2+dir[i][0]==tx2&&ty2+dir[i][1]==ty2&&((tx1!=hx1||ty1!=hy1)&&(tx2!=hx2||ty2!=hy2)) )
goto next2;
else if(m[tx2+dir[i][0]][ty2+dir[i][1]]==-1)
{
// m[tx2+dir[i][0]][ty2+dir[i][1]]=0;
// m[tx2][ty2]=0;
tx2+=dir[i][0];
ty2+=dir[i][1];
}
else if(m[tx2+dir[i][0]][ty2+dir[i][1]]==0&&(tx2+dir[i][0]!=tx1||ty2+dir[i][1]!=ty1))
{
// m[tx2+dir[i][0]][ty2+dir[i][1]]=1;
// m[tx2][ty2]=0;
tx2+=dir[i][0];
ty2+=dir[i][1];
}
next2:
if(!v[tx1][ty1][tx2][ty2])
{
v[tx1][ty1][tx2][ty2]=true;
v[tx2][ty2][tx1][ty1]=true;
tt++;
rear++;
l[rear].x1=tx1;
l[rear].y1=ty1;
l[rear].x2=tx2;
l[rear].y2=ty2;
l[rear].time=tt;
}
}
front++;
}
if(front>rear)
printf("Sorry , sir , my poor program fails to get an answer.\n");
else
printf("%d\n",l[front].time);
}
return 0;
}
最后一題，解題報(bào)告上貌似是直接建圖做的 我感覺并差集反而更簡單
#include<iostream>
using namespace std;
#define N 100001
int f[N];
int r[N];
bool mark[N];
int find(int n)
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}//查找函數(shù)，并壓縮路徑
int Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
else
{
f[a]=b;
r[b]+=(r[a]+1);
}
return 1;
}//合并函數(shù)，如果屬于同一分支則返回0，成功合并返回1
int main()
{
int n;
int i;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
f[i]=i;
r[i]=0;
}
memset(mark,false,sizeof(bool)*n);
int temp;
for(i=0;i<n;i++)
{
scanf("%d",&temp);
if(i!=temp)
{
if(Union(i,temp))
{
mark[i]=true;
}
else
{
mark[i]=true;
}
}
else
r[i]+=1;
}
int mm=0;
int ma=0;
for(i=0;i<n;i++)
{
if(mark[i]==false&&r[i]>mm)
{
mm=r[i];
ma=i;
}
}
if(mm==0)
{
printf("Trouble\n");
continue;
}
int cnt=0;
for(i=0;i<n;i++)
{
if(mark[i]==false&&r[i]==mm)
cnt++;
}
if(cnt>1)
{
printf("Trouble\n");
continue;
}
else
printf("%d\n",ma);
}
return 0;
}