infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
http://acm.pku.edu.cn/JudgeOnline/problem?id=2312
poj 2312 Battle City
简单的BFS





Source Code

Problem: 2312 User: lovecanon
Memory: 1244K Time: 16MS
Language: GCC Result: Accepted

#include<stdio.h>
typedef 
struct node 
{
    
int x;
    
int y;
}node;
node Q[
100000];
char board[301][301];
int step[301][301];
int m,n;
const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};

int ok(int x,int y)
{
    
if(x>=0&&x<m&&y>=0&&y<n) return 1;
    
else return 0;
}

void solve(int x1,int y1,int x2,int y2)
{
    
int i,j,cntx,cnty,nextx,nexty,head,tail,tmp,minstep=0x7fffffff;
    cntx
=x1;cnty=y1;head=tail=0;
    
for(i=0;i<m;i++)
        
for(j=0;j<n;j++)
            step[i][j]
=0x7fffffff;
    step[cntx][cnty]
=0;

    
while(1)
    {
        
for(i=0;i<4;i++)
        {
            nextx
=cntx+dx[i];
            nexty
=cnty+dy[i];
            
if(ok(nextx,nexty))
            {
                
if(board[nextx][nexty]=='E')
                {
                    tmp
=step[cntx][cnty]+1;
                    
if(tmp<step[nextx][nexty])
                    {
                        step[nextx][nexty]
=tmp;
                        Q[
++tail].x=nextx;
                        Q[tail].y
=nexty;
                    }
                }
                
if(board[nextx][nexty]=='B')
                {
                    tmp
=step[cntx][cnty]+2;
                    
if(tmp<step[nextx][nexty])
                    {
                        step[nextx][nexty]
=tmp;
                        Q[
++tail].x=nextx;
                        Q[tail].y
=nexty;
                    }
                }
                
if(board[nextx][nexty]=='T')
                {
                    
if(step[cntx][cnty]+1<minstep)  minstep=step[cntx][cnty]+1;
                }
            }
        }
        
if(head==tail)  break;
        
else
        {
            cntx
=Q[++head].x;
            cnty
=Q[head].y;
        }
 
    }
    
if(minstep==0x7fffffff)  printf("-1\n");
    
else printf("%d\n",minstep);

}

int main()
{
    
while(1)
    {
        
int i,j;
        
int x1,y1,x2,y2;

        scanf(
"%d%d",&m,&n);
        getchar();

        
if(m==0&&n==0return 0;

        
for(i=0;i<m;i++)
        {
            
for(j=0;j<n;j++)
            {
                board[i][j]
=getchar();
                
if(board[i][j]=='Y')
                {
                    x1
=i;y1=j;
                }
                
if(board[i][j]=='T')
                {
                    x2
=i;y2=j;
                }
            }
            getchar();
        }
        solve(x1,y1,x2,y2);
    }
    
return 0;

}

posted on 2008-09-20 04:38 infinity 阅读(534) 评论(1)  编辑 收藏 引用 所属分类: acm

评论

# re: poj 2312 Battle City 2012-09-16 22:31 ty78
我用X代表列 Y代表行 为什么会错?
我都把X,Y相关的替换?能说明下嘛,我是个菜鸟
#include<stdio.h>
typedef struct node
{
int x;
int y;
}node;
node Q[100000];
char board[301][301];
int step[301][301];
int m,n;
const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};

int ok(int x,int y)
{
if(x>=0&&x<m&&y>=0&&y<n) return 1;
else return 0;
}

void solve(int x1,int y1,int x2,int y2)
{
int i,j,cntx,cnty,nextx,nexty,head,tail,tmp,minstep=0x7fffffff;
cntx=x1;cnty=y1;head=tail=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
step[i][j]=0x7fffffff;
step[cnty][cntx]=0;

while(1)
{
for(i=0;i<4;i++)
{
nextx=cntx+dx[i];
nexty=cnty+dy[i];
if(ok(nextx,nexty))
{
if(board[nexty][nextx]=='E')
{
tmp=step[cnty][cntx]+1;
if(tmp<step[nexty][nextx])
{
step[nexty][nextx]=tmp;
Q[++tail].x=nextx;
Q[tail].y=nexty;
}
}
if(board[nexty][nextx]=='B')
{
tmp=step[cnty][cntx]+2;
if(tmp<step[nexty][nextx])
{
step[nexty][nextx]=tmp;
Q[++tail].x=nextx;
Q[tail].y=nexty;
}
}
if(board[nexty][nextx]=='T')
{
if(step[cnty][cntx]+1<minstep) minstep=step[cnty][cntx]+1;
}
}
}
if(head==tail) break;
else
{
cntx=Q[++head].x;
cnty=Q[head].y;
}

}
if(minstep==0x7fffffff) printf("-1\n");
else printf("%d\n",minstep);

}

int main()
{
while(1)
{
int i,j;
int x1,y1,x2,y2;

scanf("%d%d",&m,&n);
getchar();

if(m==0&&n==0) return 0;

for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
board[i][j]=getchar();
if(board[i][j]=='Y')
{
x1=j;y1=i;
}
if(board[i][j]=='T')
{
x2=i;y2=j;
}
}
getchar();
}
solve(x1,y1,x2,y2);
}
return 0;

}

  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理