很好玩的一个游戏,建议大家做完了去玩一玩~。
方块的状态有3种情况,竖着,横躺着,竖躺着,所以可以用一个标记变量表示。
对于判重,可以开一个三维的数组来判断。
麻烦的地方在于移动,如果直接模拟的话,将会产生很大的代码量。250~300行左右……
可以开几个辅助数组,直接判断上下左右时相应的坐标变化。
写辅助数组时最好头脑清醒,写错了某个的话,debug都很困难。。。(可以注意上下的对称性)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
char map[505][505];
int endx,endy;
struct node
{
int dis;
int flag; //0=竖着,1=横躺着,2=竖躺着
int x1;
int y1;
int x2;
int y2;
}start;
node q[1000000];
bool vis[505][505][3];
int dx1[3][4]={{-2,1,0,0},{-1,1,0,0},{-1,2,0,0}};
int dy1[3][4]={{0,0,-2,1},{0,0,-1,2},{0,0,-1,1}};
int ddx[4]={-1,1,0,0};
int ddy[4]={0,0,-1,1};
int dx2[3][4]={{-1,2,0,0},{-1,1,0,0},{-2,1,0,0}};
int dy2[3][4]={{0,0,-1,2},{0,0,-2,1},{0,0,-1,1}};
int c[3][4]={{2,2,1,1},{1,1,0,0},{0,0,2,2}};
int n,m;
bool f(int x,int y)
{
return x>=0&&x<n&&y>=0&&y<m;
}
bool isok(node &t)
{
if(!f(t.x1,t.y1)||!f(t.x2,t.y2)) return false;
if(t.flag==0&&map[t.x1][t.y1]=='E') return false;
if(map[t.x1][t.y1]=='#'||map[t.x2][t.y2]=='#') return false;
return true;
}
void creat()
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(map[i][j]=='O')
{
endx=i;endy=j;
}
else if(map[i][j]=='X')
{
start.x2=start.x1=i;start.y2=start.y1=j;
int rx=i+ddx[3],ry=j+ddy[3];
int dx=i+ddx[1],dy=j+ddy[1];
if(f(rx,ry)&&map[rx][ry]=='X')
{
start.flag=1;
start.x2=rx;start.y2=ry;
map[i][j]=map[rx][ry]='.';
}
else if(f(dx,dy)&&map[dx][dy]=='X')
{
start.flag=2;
start.x2=dx;start.y2=dy;
map[i][j]=map[dx][dy]='.';
}
else
{
start.flag=0;
map[i][j]='.';
}
}
}
start.dis=0;
}
bool expend(node &t,int d)
{
t.x1+=dx1[t.flag][d];
t.y1+=dy1[t.flag][d];
t.x2+=dx2[t.flag][d];
t.y2+=dy2[t.flag][d];
t.dis++;
t.flag=c[t.flag][d];
if(!isok(t)) return false;
if(!vis[t.x1][t.y1][t.flag])
{
vis[t.x1][t.y1][t.flag]=1;
return true;
}
return false;
}
void bfs()
{
int rear=0,front=0;
q[rear++]=start;
node f,r;
while(front<rear)
{
f=q[front];
for(int d=0;d<4;d++)
{
r=f;
if(expend(r,d))
{
q[rear++]=r;
if(r.x1==endx&&r.y1==endy&&r.flag==0)
{
printf("%d\n",r.dis);
return;
}
}
}
front++;
}
printf("Impossible\n");
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!n&&!m) break;
for(int i=0;i<n;i++)
{
scanf("%s",map[i]);
}
memset(vis,0,sizeof(vis));
creat();
bfs();
}
return 0;
}
900多ms很不满意,直接把原代码改成了双搜,竟然还是800多ms。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
char map[505][505];
int endx,endy;
struct node
{
int dis;
int flag; //0=竖着,1=横躺着,2=竖躺着
int x1;
int y1;
int x2;
int y2;
}start,end;
node q1[1000000];
node q2[1000000];
int vis[505][505][3];
int vis2[505][505][3];
int dx1[3][4]={{-2,1,0,0},{-1,1,0,0},{-1,2,0,0}};
int dy1[3][4]={{0,0,-2,1},{0,0,-1,2},{0,0,-1,1}};
int ddx[4]={-1,1,0,0};
int ddy[4]={0,0,-1,1};
int dx2[3][4]={{-1,2,0,0},{-1,1,0,0},{-2,1,0,0}};
int dy2[3][4]={{0,0,-1,2},{0,0,-2,1},{0,0,-1,1}};
int c[3][4]={{2,2,1,1},{1,1,0,0},{0,0,2,2}};
int n,m;
bool f(int x,int y)
{
return x>=0&&x<n&&y>=0&&y<m;
}
bool isok(node &t)
{
if(!f(t.x1,t.y1)||!f(t.x2,t.y2)) return false;
if(t.flag==0&&map[t.x1][t.y1]=='E') return false;
if(map[t.x1][t.y1]=='#'||map[t.x2][t.y2]=='#') return false;
return true;
}
void creat()
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(map[i][j]=='O')
{
endx=i;endy=j;
end.x1=end.x2=i;
end.y1=end.y2=j;
end.flag=0;
end.dis=0;
}
else if(map[i][j]=='X')
{
start.x2=start.x1=i;start.y2=start.y1=j;
int rx=i+ddx[3],ry=j+ddy[3];
int dx=i+ddx[1],dy=j+ddy[1];
if(f(rx,ry)&&map[rx][ry]=='X')
{
start.flag=1;
start.x2=rx;start.y2=ry;
map[i][j]=map[rx][ry]='.';
}
else if(f(dx,dy)&&map[dx][dy]=='X')
{
start.flag=2;
start.x2=dx;start.y2=dy;
map[i][j]=map[dx][dy]='.';
}
else
{
start.flag=0;
map[i][j]='.';
}
}
}
start.dis=0;
}
bool expend(node &t,int d)
{
t.x1+=dx1[t.flag][d];
t.y1+=dy1[t.flag][d];
t.x2+=dx2[t.flag][d];
t.y2+=dy2[t.flag][d];
t.dis++;
t.flag=c[t.flag][d];
if(!isok(t)) return false;
return true;
}
void bfs()
{
int rear1=0,front1=0;
q1[rear1++]=start;
int rear2=0,front2=0;
q2[rear2++]=end;
node f1,r1,f2,r2;
int k1=1,kk1=0,k2=1,kk2=0;
while(front1<rear1&&front2<rear2)
{
while(k1--){
f1=q1[front1];front1++;
for(int d=0;d<4;d++)
{
r1=f1;
if(expend(r1,d))
{
if(vis2[r1.x1][r1.y1][r1.flag])
{
if(vis2[r1.x1][r1.y1][r1.flag]==-1)
vis2[r1.x1][r1.y1][r1.flag]=0;
printf("%d\n",r1.dis+vis2[r1.x1][r1.y1][r1.flag]);
return;
}
if(!vis[r1.x1][r1.y1][r1.flag])
{
vis[r1.x1][r1.y1][r1.flag]=r1.dis;
q1[rear1++]=r1;
kk1++;
}
}
}
}
k1=kk1;kk1=0;
while(k2--)
{
f2=q2[front2];front2++;
for(int d=0;d<4;d++)
{
r2=f2;
if(expend(r2,d))
{
if(vis[r2.x1][r2.y1][r2.flag])
{
if(vis[r2.x1][r2.y1][r2.flag]==-1)
vis[r2.x1][r2.y1][r2.flag]=0;
printf("%d\n",r2.dis+vis[r2.x1][r2.y1][r2.flag]);
return;
}
if(!vis2[r2.x1][r2.y1][r2.flag])
{
vis2[r2.x1][r2.y1][r2.flag]=r2.dis;
q2[rear2++]=r2;
kk2++;
}
}
}
}
k2=kk2;
kk2=0;
}
printf("Impossible\n");
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!n&&!m) break;
for(int i=0;i<n;i++)
{
scanf("%s",map[i]);
}
memset(vis,0,sizeof(vis));
memset(vis2,0,sizeof(vis2));
creat();
vis2[end.x1][end.y1][end.flag]=-1;
vis[start.x1][start.y1][start.flag]=-1;
bfs();
}
return 0;
}
分享到:
相关推荐
在代码实现上,`POJ1426-Find The Multiple【table】.cpp`可能包含了利用数组或哈希表来存储和查找结果的策略,而`POJ1426-Find The Multiple【BFS+同余模】.cpp`则是直接使用BFS和模运算的实现。文档`POJ1426-Find ...
在提交的代码文件“POJ3026-Borg Maze【BFS+Prim】.cpp”中,我们可以看到如何将这两种算法结合在一起,解决“Borg Maze”问题的具体实现细节。文档“POJ3026-Borg Maze【BFS+Prim】.doc”则可能包含了对解题思路的...
标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...
"西北工业大学POJ试题C++答案代码+课程设计"这一标题表明了资源的主要内容,涉及两个核心部分:一是西北工业大学的编程竞赛(POJ,Problem Oriented Judge System)的C++解题代码,二是与这些题目相关的课程设计。...
《POJ1207-The 3n + 1 problem》是北京大学在线编程平台POJ上的一道经典算法题目,其主要涉及的知识点是数论和动态规划。本题目的核心是解决著名的“Collatz Conjecture”问题,也被称为“3n+1猜想”。 3n+1猜想是...
在"POJ3322_Code.cpp"这个文件中,很可能包含了实现上述宽搜算法的C++代码。通过阅读和分析这个代码,我们可以了解到如何具体处理矩形方块的移动,如何构建和更新搜索空间,以及如何判断是否到达目标位置等细节。这...
- **实现难度**:树状数组的实现更为简单,代码量较少;而线段树则需要更多的逻辑处理。 - **性能**:在实际运行效率上,两者相差不大。但在某些特定场景下,线段树可以提供更多的功能支持。 - **可读性**:树状数组...
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...
【描述】"北大POJ1005-I Think I Need a Houseboat 解题报告+AC代码" 暗示了解决此问题的完整流程,包括理解问题、设计解决方案、编写代码以及最终获得Accepted(AC)状态的代码。解题报告通常会包含问题分析、算法...
【北大POJ初级-简单搜索】是北京大学在线判题系统POJ(Problem Online Judge)针对初学者设置的一类编程题目,主要涉及基础的算法和数据结构应用。这类问题通常不会过于复杂,旨在帮助学习者掌握基本的编程思维和...
题目"POJ-2870 Light Up"是一个经典的图论问题,主要涉及深度优先搜索(DFS)算法的运用。该问题要求点亮一个矩形区域内的所有障碍物,每个障碍物需要特定数量的灯光才能被照亮,且相邻的障碍物之间不能有空格。题目...
提供的`Main.java`文件应该是实现树状数组解决POJ 3067问题的代码。主要包含两个核心函数,一个是`update(int pos, int val)`用于更新操作,另一个是`query(int l, int r)`用于查询操作。此外,可能还有一个`main`...
在POJ 2029这个题目中,`Main.java`文件可能包含了实现二维树状数组的代码。通常,代码会包含以下几个关键步骤: 1. **初始化**:创建一个足够大的一维数组C[],并用初始值填充。 2. **更新**:对于一个元素(x, y)...
描述中提到的链接指向了一篇博客文章,尽管具体内容没有提供,但可以推测博主分享了他们如何使用滚动数组来解决POJ 1159问题的思路和源代码。通常,这类博客会包含对问题的解析、动态规划的状态转移方程以及如何利用...
标题中的"poj_2682(3).rar"是一个指向编程竞赛问题的引用,通常这类问题在网站如POJ(Programming Online Judge)上出现,供程序员解决并提交代码进行测试。这个问题的编号是2682,可能涉及到特定的数据结构或算法...
两个解决方案的代码文件“POJ1753-Flip Game(BFS+bit).cpp”和“POJ1753-Flip Game(DFS+enum).cpp”分别实现了BFS和DFS策略。阅读这些代码可以帮助理解如何将理论转换为实际的程序实现。 五、文档说明 “POJ1753-...
根据标题“poj 1191 经典dp 源代码”和描述中的信息,可以推测此题目是一个经典的动态规划问题。题目要求通过划分一个二维矩阵为多个不重叠的矩形区域,使得每个矩形区域的平均值与整体平均值之差的平方和最小。这个...
结合这些信息,我们可以推断,这个压缩包可能包含了NOI2002比赛中关于“dragon”问题的一些资源,如题目描述、样例输入/输出、可能的参考代码等,同时还有在POJ平台上使用BFS算法实现的AC程序。对于学习和研究算法,...