 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
自己觉得没错，不知道哪里还有问题，哪位给点测试数据#include<iostream>
#include<queue>
#define MAX 999999999
using namespace std;
//把状态分成三种进行标记，
//对于横纵的放置要判断连续两格是否非空且不越界，且这两格不全被遍历过在当前状态下
//状态1是站立，状态2是横放，状态3是竖放
int n,m;
int tx,ty;
char b[501][501];
int map[501][501][4];
typedef struct Node
{
int x[2];
int y[2];
int len;
int v;
}Node;
queue<Node>q;
bool check(int x1,int y1)//判断是否在地图内
{
if(x1>0&&x1<=n&&y1>0&&y1<=m)return 1;
return 0;
}
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
bool bfs()
{
Node s,t;
s=q.front();
q.pop();
int len,temp,r,i,j,k,max,min;
len=s.len;
/* cout<<"状态："<<len<<endl;
for(i=0;i<len;i++)
{
cout<<"x="<<s.x[i]<<" y="<<s.y[i]<<endl;
}*/
if(len==2)//两个块
{
if(s.x[0]==s.x[1])//横放的
{
t.x[0]=s.x[0]+1;//上
t.x[1]=s.x[1]+1;
t.y[0]=s.y[0];
t.y[1]=s.y[1];
t.len=2;
t.v=s.v+1;
r=0;
for(i=0;i<2;i++)
{
if(check(t.x[i],t.y[i])&&b[t.x[i]][t.y[i]]!='#')continue;//在地图内且该点还没到达过且不是空格子
else {r=1;break;}
}
if(r==0)
{
if(map[t.x[0]][t.y[0]][2]==1&&map[t.x[1]][t.y[1]][2]==1)r=1;
}
if(r==0)
{
map[t.x[0]][t.y[0]][2]=1;
map[t.x[1]][t.y[1]][2]=1;
q.push(t);
}
t.x[0]=s.x[0]-1;//下
t.x[1]=s.x[1]-1;
t.y[0]=s.y[0];
t.y[1]=s.y[1];
t.len=2;
t.v=s.v+1;
/* if(t.x[0]==6)
{
cout<<"******"<<endl;
for(i=0;i<len;i++)
{
cout<<"x="<<t.x[i]<<" y="<<t.y[i]<<endl;
}
system("pause");
}*/
r=0;
for(i=0;i<2;i++)
{
if(check(t.x[i],t.y[i])&&b[t.x[i]][t.y[i]]!='#')continue;//在地图内且该点还没到达过且不是空
else {r=1;break;}
}
if(r==0)
{
if(map[t.x[0]][t.y[0]][2]==1&&map[t.x[1]][t.y[1]][2]==1)r=1;
}
if(r==0)
{
map[t.x[0]][t.y[0]][2]=1;
map[t.x[1]][t.y[1]][2]=1;
q.push(t);
}
max=s.y[0];
min=s.y[1];
if(max<min)
{
r=max;max=min;min=r;
}
t.x[0]=s.x[0];
t.y[0]=min-1;//左，此时是单个，要考虑到目标点的情况
t.len=1;
t.v=s.v+1;
if(check(t.x[0],t.y[0])&&(b[t.x[0]][t.y[0]]!='E'&&b[t.x[0]][t.y[0]]!='#')&&map[t.x[0]][t.y[0]][1]==0)
//1状态格子不能为空且不能为脆弱的 ,且当前状态没到达过
{
if(b[t.x[0]][t.y[0]]=='O')//目标点
{
printf("%d\n",t.v);
return 0;
}
map[t.x[0]][t.y[0]][1]=1;
q.push(t);
}
t.x[0]=s.x[0];
t.y[0]=max+1;//右
t.len=1;
t.v=s.v+1;
if(check(t.x[0],t.y[0])&&(b[t.x[0]][t.y[0]]!='E'&&b[t.x[0]][t.y[0]]!='#')&&map[t.x[0]][t.y[0]][1]==0)
{
if(b[t.x[0]][t.y[0]]=='O')
{
printf("%d\n",t.v);
return 0;
}
map[t.x[0]][t.y[0]][1]=1;
q.push(t);
}
}
else if(s.y[0]==s.y[1])//竖放的
{
t.y[0]=s.y[0]+1;//右
t.y[1]=s.y[1]+1;
t.x[0]=s.x[0];
t.x[1]=s.x[1];
t.len=2;
t.v=s.v+1;
r=0;
for(i=0;i<2;i++)
{
if(check(t.x[i],t.y[i])&&b[t.x[i]][t.y[i]]!='#')continue;//在地图内且该点还没到达过且不是空
else {r=1;break;}
}
if(r==0)
{
if(map[t.x[0]][t.y[0]][3]==1&&map[t.x[1]][t.y[1]][3]==1)r=1;
}
if(r==0)
{
map[t.x[0]][t.y[0]][3]=1;
map[t.x[1]][t.y[1]][3]=1;
q.push(t);
}
t.y[0]=s.y[0]-1;//左
t.y[1]=s.y[1]-1;
t.x[0]=s.x[0];
t.x[1]=s.x[1];
t.len=2;
t.v=s.v+1;
r=0;
for(i=0;i<2;i++)
{
if(check(t.x[i],t.y[i])&&b[t.x[i]][t.y[i]]!='#')continue;//在地图内且该点还没到达过且不是空
else {r=1;break;}
}
if(r==0)
{
if(map[t.x[0]][t.y[0]][3]==1&&map[t.x[1]][t.y[1]][3]==1)r=1;
}
if(r==0)
{
map[t.x[0]][t.y[0]][3]=1;
map[t.x[1]][t.y[1]][3]=1;
q.push(t);
}
max=s.x[0];
min=s.x[1];
if(max<min)
{
r=max;max=min;min=r;
}
t.x[0]=min-1;
t.y[0]=s.y[0];//上，此时是单个，要考虑到目标点的情况
t.len=1;
t.v=s.v+1;
if(check(t.x[0],t.y[0])&&(b[t.x[0]][t.y[0]]!='E'&&b[t.x[0]][t.y[0]]!='#')&&map[t.x[0]][t.y[0]][1]==0)
{
if(b[t.x[0]][t.y[0]]=='O')
{
printf("%d\n",t.v);
return 0;
}
map[t.x[0]][t.y[0]][1]=1;
q.push(t);
}
t.x[0]=max+1;
t.y[0]=s.y[0];//下
t.len=1;
t.v=s.v+1;
if(check(t.x[0],t.y[0])&&(b[t.x[0]][t.y[0]]!='E'&&b[t.x[0]][t.y[0]]!='#')&&map[t.x[0]][t.y[0]][1]==0)
{
if(b[t.x[0]][t.y[0]]=='O')
{
printf("%d\n",t.v);
return 0;
}
map[t.x[0]][t.y[0]][1]=1;
q.push(t);
}
}
}
else
{
for(i=0;i<4;i++)
{
t.x[0]=s.x[0]+dx[i];
t.y[0]=s.y[0]+dy[i];
t.x[1]=t.x[0]+dx[i];
t.y[1]=t.y[0]+dy[i];
t.len=2;
t.v=s.v+1;
r=0;
int key=3;
if(t.x[0]==t.x[1])key=2;
for(k=0;k<2;k++)
{
if(check(t.x[k],t.y[k])&&b[t.x[k]][t.y[k]]!='#')continue;
else {r=1;break;}
}
if(r==0)
{
if(map[t.x[0]][t.y[0]][key]==1&&map[t.x[1]][t.y[1]][key]==1)r=1;
}
if(r==0)
{
map[t.x[0]][t.y[0]][key]=1;
map[t.x[1]][t.y[1]][key]=1;
q.push(t);
}
}
}
// system("pause");
if(q.empty())
{
printf("Impossible\n");
return 0;
}
return 1;
}
int main()
{
int i,j,k,len,flag;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0)break;
for(i=1;i<=n;i++)
{
scanf("%s",b[i]+1);
}
len=0;
Node t;
t.v=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(b[i][j]=='X')
{
t.x[len]=i;
t.y[len]=j;
len++;
}
if(b[i][j]=='O')
{
tx=i;
ty=j;
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
for(k=1;k<=3;k++)
{
map[i][j][k]=0;
}
}
}
t.len=len;
if(len==2)
{
int key=3;
if(t.x[0]==t.x[1])key=2;
map[t.x[0]][t.y[0]][key]=1;
map[t.x[1]][t.y[1]][key]=1;
}
else if(len==1)
{
map[t.x[0]][t.y[0]][1]=1;
}
while(!q.empty())q.pop();
q.push(t);
flag=1;
while(flag)
{
flag=bfs();
}
}
return 0;
}
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
