Poj Solution 1307

http://poj.org/problem?id=1307

#include"stdio.h"
bool left[13][13];
bool right[13][13];
bool up[13][13];
bool down[13][13];
int n,m,x1,x2,y1,y2;

bool init()
{
    int i,j,s;
    
    scanf("%d %d %d %d %d %d",&n,&m,&x1,&y1,&x2,&y2);

    if(n==0&&m==0&&x1==0&&x2==0&&y1==0&&y2==0)
        return 0;

    x1--,x2--,y1--,y2--;    
    
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
    {
        scanf("%d",&s);
        right[i][j] = left[i][j+1]= (s&1);
        down[i][j] = up[i+1][j]= (s&2);
    }

    for(i=0;i<n;i++)
        left[i][0]=true,right[i][m-1]=true;
    for(j=0;j<m;j++)
        up[0][j]=true,down[n-1][j]=true;

    return 1;
}

int sign[13][13];
bool (*pt[])[13]={left,up,right,down};
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};


bool search(int x,int y,int step)
{
    int i;

    sign[x][y]=step;
    
    if(x==x2&&y==y2)return 1;
    
    for(i=0;i<4;i++)
        if( !pt[i][x][y] && sign[x+dx[i]][y+dy[i]]==0 )
        {
            if(search(x+dx[i],y+dy[i],step+1))
                return 1;    
        }
    
    sign[x][y] = -1;
    
    return 0;
}

void doit()
{
    int i,j;
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        sign[i][j]=0;
    search(x1,y1,1);
}

void printmap()
{
    int i,j;
    static  int times=1;
    
    printf("Maze %dnn",times++);    
           
    printf("+");
     
    for(j=0;j<m;j++)
    {
        printf("---+");
    }
    
    for(i=0;i<n;i++)
    {
        printf("n|");
        for(j=0;j<m;j++)
        {
            if(sign[i][j]>0)printf("%3d",sign[i][j]);
            else if(sign[i][j]==-1)printf("???");
            else printf("   ");
            
            if(right[i][j])printf("|");
            else printf(" ");
        }

        printf("n+");
        for(j=0;j<m;j++)
        {
        
            if(down[i][j])printf("---");
            else printf("   ");
            printf("+");
        }
    }
    printf("nnn");
}

int main()
{
    while(init())
    {
        doit();
        printmap();
    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *