| ||||||||||
| 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