其实这个题挺基础的，想到了把结构体设置成两个人的坐标&时间，也想到了两个人的位置也需要不能走重复，但是悲剧的设置成了三维的，但是……我们需要的是这两人不能走过之前的位置，注意，是，俩人的位置不能同时与之前某一时间的相同！所以要设置成四维的
再就是，能从0开始就不要从1开始读入数组……
忧伤啊
WA的 各位看官猜猜哪里错了~。~果然就是从“1”开始这个地方错了→_→ 细心啊啊啊啊啊
/***********
hdu2216
2015.12.7-2015.12.8
***********/
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int m,n;
int z1,z2,s1,s2;
char map[25][25];
int vis[25][25][25][25];
int to[4][2] = {1,0,-1,0,0,-1,0,1};//Z的走法
int to2[4][2] = {-1,0,1,0,0,1,0,-1};//S走相反路线
struct node
{
int x1,x2,y1,y2,step;
};
int check(int x,int y)
{
if(x<0 || y<0 || x>=n || y>=m || map[x][y] == 'X')
return 1;
return 0;
}
int judge(int x,int x1,int y,int y1)//符合条件的状况
{
if(x == x1 && y == y1)
return 1;
if(x == x1+1 && y == y1)
return 1;
if(x == x1-1 && y == y1)
return 1;
if(x == x1 && y == y1-1)
return 1;
if(x == x1 && y == y1+1)
return 1;
return 0;
}
int bfs()
{
queue<node> Q;
node cur,next;
cur.x1=z1,cur.y1=z2,cur.x2=s1,cur.y2=s2,cur.step=0;
vis[z1][z2][s1][s2]=1;
Q.push(cur);
while(!Q.empty())
{
cur=Q.front();//普通队列的头不叫pop ！！
// printf("zx=%d zy=%d sx=%d sy=%d step=%d\n",cur.zx,cur.zy,cur.sx,cur.sy,cur.step);
Q.pop();
if(judge(cur.x1,cur.x2,cur.y1,cur.y2)) return cur.step;
for(int i=0;i<4;i++)
{
next=cur;
next.x1+=to[i][0];
next.y1+=to[i][1];
next.x2+=to2[i][0];
next.y2+=to2[i][1];
if(check(next.x1,next.y1)) continue;
// if(judge(next)) return next.step;
if(check(next.x2,next.y2))
{
next.x2=cur.x2;
next.y2=cur.y2;
}
if(vis[next.x1][next.y1][next.x2][next.y2]) continue;
vis[next.x1][next.y1][next.x2][next.y2]=1;
next.step=cur.step+1;
Q.push(next);
}
}
return -1;
}
int main()
{
// freopen("cin.txt","r",stdin);
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;i++)
{
scanf("%s",map[i]+1);
for(int j=1;j<=m;j++)
{
if(map[i][j]=='Z') map[i][j]='.',z1=i,z2=j;
if(map[i][j]=='S') map[i][j]='.',s1=i,s2=j;
}
}
memset(vis,0,sizeof(vis));
int ans=bfs();
if(ans!=-1)printf("%d\n",ans);
else printf("Bad Luck!\n");
}
return 0;
}
AC的
/***********
hdu2216
2015.12.7-2015.12.8
***********/
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int m,n;
int z1,z2,s1,s2;
char map[25][25];
int vis[25][25][25][25];
int to[4][2] = {1,0,-1,0,0,-1,0,1};//Z的走法
int to2[4][2] = {-1,0,1,0,0,1,0,-1};//S走相反路线
struct node
{
int x1,x2,y1,y2,step;
};
int check(int x,int y)
{
if(x<0 || y<0 || x>=n || y>=m || map[x][y] == 'X')
return 1;
return 0;
}
int judge(int x,int x1,int y,int y1)//符合条件的状况
{
if(x == x1 && y == y1)
return 1;
if(x == x1+1 && y == y1)
return 1;
if(x == x1-1 && y == y1)
return 1;
if(x == x1 && y == y1-1)
return 1;
if(x == x1 && y == y1+1)
return 1;
return 0;
}
int bfs()
{
queue<node> Q;
node cur,next;
cur.x1=z1,cur.y1=z2,cur.x2=s1,cur.y2=s2,cur.step=0;
vis[z1][z2][s1][s2]=1;
Q.push(cur);
while(!Q.empty())
{
cur=Q.front();//普通队列的头不叫pop ！！
// printf("zx=%d zy=%d sx=%d sy=%d step=%d\n",cur.zx,cur.zy,cur.sx,cur.sy,cur.step);
Q.pop();
if(judge(cur.x1,cur.x2,cur.y1,cur.y2)) return cur.step;
for(int i=0;i<4;i++)
{
next=cur;
next.x1=cur.x1+to[i][0];
next.y1=cur.y1+to[i][1];
next.x2=cur.x2+to2[i][0];
next.y2=cur.y2+to2[i][1];
if(check(next.x1,next.y1)) continue;
// if(judge(next)) return next.step;
if(check(next.x2,next.y2))
{
next.x2=cur.x2;
next.y2=cur.y2;
}
if(vis[next.x1][next.y1][next.x2][next.y2]) continue;
vis[next.x1][next.y1][next.x2][next.y2]=1;
next.step=cur.step+1;
Q.push(next);
}
}
return -1;
}
int main()
{
// freopen("cin.txt","r",stdin);
while(~scanf("%d%d",&n,&m))
{
for(int i=0;i<n;i++)
{
scanf("%s",map[i]);
for(int j=0;j<m;j++)
{
if(map[i][j]=='Z') map[i][j]='.',z1=i,z2=j;
if(map[i][j]=='S') map[i][j]='.',s1=i,s2=j;
}
}
memset(vis,0,sizeof(vis));
int ans=bfs();
if(ans!=-1)printf("%d\n",ans);
else printf("Bad Luck!\n");
}
return 0;
}
自己AC的~
| 0MS | 2424K | 2374 B |
#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct node
{
int zx,zy,sx,sy,step;
};
char str[30][30];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int n,m,z_x,z_y,s_x,s_y;
bool vis[30][30][30][30];
bool judge(node a)
{
if(a.zx==a.sx&&a.zy==a.sy)return 1;
if(a.zx==a.sx+1&&a.zy==a.sy) return 1;
if(a.zx+1==a.sx&&a.zy==a.sy) return 1;
if(a.zx==a.sx&&a.zy==a.sy+1) return 1;
if(a.zx==a.sx&&a.zy==a.sy-1) return 1;
return 0;
}
bool jud0(int z_x,int z_y)
{
if(z_x<1||z_x>n||z_y<1||z_y>m||str[z_x][z_y]=='X') return 1;
return 0;
}
bool jug1(int z_x,int z_y,int s_x,int s_y)
{
if(vis[z_x][z_y][s_x][s_y]||str[z_x][z_y]=='X') return 1;
if(s_x<0||s_x>n||s_y<0||s_y>m||str[s_x][s_y]=='X')return 1;
return 0;
}
int bfs()
{
queue<node> Q;
node cur,next;
cur.zx=z_x,cur.zy=z_y,cur.sx=s_x,cur.sy=s_y,cur.step=0;
vis[z_x][z_y][s_x][s_y]=1;
Q.push(cur);
while(!Q.empty())
{
cur=Q.front();//普通队列的头不叫pop ！！
// printf("zx=%d zy=%d sx=%d sy=%d step=%d\n",cur.zx,cur.zy,cur.sx,cur.sy,cur.step);
Q.pop();
if(judge(cur)) return cur.step;
for(int i=0;i<4;i++)
{
next=cur;
next.step++;
next.zx+=dir[i][0];
next.zy+=dir[i][1];
if(jud0(next.zx,next.zy)) continue;
// if(judge(next)) return next.step;
next.sx-=dir[i][0];
next.sy-=dir[i][1];
if(jud0(next.sx,next.sy))
{
next.sx+=dir[i][0];
next.sy+=dir[i][1];
}
if(vis[next.zx][next.zy][next.sx][next.sy]) continue;
vis[next.zx][next.zy][next.sx][next.sy]=1;
Q.push(next);
}
}
return -1;
}
int main()
{
// freopen("cin.txt","r",stdin);
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;i++)
{
scanf("%s",str[i]+1);
for(int j=1;j<=m;j++)
{
if(str[i][j]=='Z') z_x=i,z_y=j;
if(str[i][j]=='S') s_x=i,s_y=j;
}
}
memset(vis,0,sizeof(vis));
int ans=bfs();
if(ans!=-1)printf("%d\n",ans);
else printf("Bad Luck!\n");
}
return 0;
}
以后可长点心吧~~真要是比赛怎么办
京公网安备 11010502036488号