Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

附代码

Posted by xtu1014 at 2010-08-07 14:58:13 on Problem 2435
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator