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 |
附代码In Reply To:这题N和E的意思好像不明确,Description和Input中互相矛盾。 Posted by:00403022 at 2005-06-28 16:26:58 #include<iostream> #include<queue> using namespace std; bool visited[100][100]; char a[100][100],dir[4]={'N','W','S','E'}; int e,n,sx,sy,ex,ey,fx[4]={-1,0,1,0},fy[4]={0,-1,0,1} ,step[10000],path[10000]; typedef struct Node{ int px,py; }Node; Node p[100][100],cur,temp; queue<Node> q; int testdir(int x,int y){ int px=p[x][y].px,py=p[x][y].py; if(p[x][y].px==-1&&p[x][y].py==-1) return -1; if(x<px&&y==py) return 0; if(x==px&&y<py) return 1; if(px<x&&y==py) return 2; return 3; } int main(){ int i,j,tx,ty,cnt=0; scanf("%d%d",&e,&n); e=2*e-1; n=2*n-1; for(i=0;i<e;i++){ getchar(); for(j=0;j<n;j++){ scanf("%c",&a[i][j]); if(a[i][j]=='S'){ sx=i; sy=j; } if(a[i][j]=='E'){ ex=i; ey=j; } } } memset(visited,false,sizeof(visited)); cur.px=sx; cur.py=sy; q.push(cur); p[sx][sy].px=-1; p[sx][sy].py=-1; while(!q.empty()){ cur=q.front(); q.pop(); if(cur.px==ex&&cur.py==ey) break; visited[cur.px][cur.py]=true; for(i=0;i<4;i++){ tx=cur.px+fx[i]; ty=cur.py+fy[i]; if(0<=tx&&tx<e&&0<=ty&&ty<n&&!visited[tx][ty]&& (a[tx][ty]=='-'||a[tx][ty]=='|'||a[tx][ty]=='E' ||a[tx][ty]=='+')){ p[tx][ty].px=cur.px; p[tx][ty].py=cur.py; temp.px=tx; temp.py=ty; q.push(temp); } } } i=0; j=0; while(cur.px!=-1&&cur.py!=-1){ j=testdir(cur.px,cur.py); if(j==-1) break; i=0; while(j==testdir(cur.px,cur.py)){ tx=cur.px; ty=cur.py; cur=p[tx][ty]; if(a[tx][ty]=='-'||a[tx][ty]=='|') i++; } path[cnt]=j; step[cnt++]=i; } for(i=cnt-1;0<=i;i--) printf("%c %d\n",dir[path[i]],step[i]); // system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator