The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

湘潭市程序設計比賽 I robot,bfs

這題出得不錯，在傳統的bfs上加了點改進，好題~

#include<iostream>

#include<cmath>

using namespace std;

int const maxn=110;

int mm[maxn][maxn];

int v[maxn][maxn][4];//0上，1右，2下，3左

struct node

{

int step;

int x,y;

int dir;

}q[10000000];

int n,m;

int t;

int sx,sy;

int tx,ty;

void input()

{

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

char s[200];

int i;

for(i=0;i<n;i++)

{

scanf("%s",s);

int len=strlen(s);

for(int j=0;j<len;j++)

{

if(s[j]=='#')mm[i][j]=-1;

else if(s[j]=='.')mm[i][j]=0;

else if(s[j]=='S'){sx=i;sy=j;mm[i][j]=0;}

else if(s[j]=='T'){tx=i;ty=j;mm[i][j]=0;}

}

bool god(int x,int y)

{

if(x>=0&&x<n&&y>=0&&y<m&&mm[x][y]!=-1)

return true;

else

return false;

}

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

int main()

{

int l,r;

int i,j;

scanf("%d",&t);

while(t--)

{

memset(v,0,sizeof(v));

input();

//

l=r=1;

q[l].step=0;

q[l].dir=0;

q[l].x=sx;

q[l].y=sy;

v[sx][sy][0]=1;

//初始化

while(l<=r)

{

if(q[l].x==tx&&q[l].y==ty)

break;

for(i=0;i<4;i++)

{

if(i==q[l].dir)

{

int nx=q[l].x+dir[i][0];

int ny=q[l].y+dir[i][1];

if(god(nx,ny)&&v[nx][ny][i]==0)

{

v[nx][ny][i]=1;

r++;

q[r].x=nx;

q[r].y=ny;

q[r].step=q[l].step+1;

q[r].dir=q[l].dir;

}

else

{

int nr=(q[l].dir+1)%4;

int nl=(((q[l].dir-1)%4+4)%4);

if(v[q[l].x][q[l].y][nr]==0)

{

v[q[l].x][q[l].y][nr]=1;

r++;

q[r].x=q[l].x;

q[r].y=q[l].y;

q[r].step=q[l].step+1;

q[r].dir=nr;

}

if(v[q[l].x][q[l].y][nl]==0)

{

v[q[l].x][q[l].y][nl]=1;

r++;

q[r].x=q[l].x;

q[r].y=q[l].y;

q[r].step=q[l].step+1;

q[r].dir=nl;

}

l++;

}

if(l<=r)

printf("%d\n",q[l].step);

else

printf("-1\n");

}

return 0;

}

posted on 2010-05-22 22:05 abilitytao 閱讀(1625) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

湘潭市程序設計比賽 I robot,bfs