Poj Solution 2458

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

#include "stdio.h"

char map[6][6];
bool sign[6][6];
int flag[6][6];
bool inline inmap( int x, int y )
{
    return 0<=x&&x<5&&0<=y&&y<5;
}
int dx[]={ 0,-1, 0, 1};
int dy[]={-1, 0, 1, 0};
int ans;
int reach;
int visit;
void find( int x, int y )
{
    int i, xx, yy;
    reach++;
    flag[x][y] = visit;

    for( i=0; i<4; i++ )
    if( inmap( xx=x+dx[i], yy=y+dy[i] ) && !sign[xx][yy] && flag[xx][yy] < visit )
    {
        find( xx, yy );
        if( reach == 7 ) return;
    }
}
void search( int j , int step , int J, int H )
{
    int i = j;
    if( H >= 4 )return;
    if( step == 7 )
    {
        reach = 0;
        visit++;
        find( i/5, i%5 );
        if( reach == 7 ) ans++;        
        return;
    }
    for( i++; i<25 &&( j<0 || ( i/5 - j/5 ) <= 1 ); i++ )
    {
        sign[i/5][i%5] = false;
        search( i, step+1, J+(int)(map[i/5][i%5]=='J'), H+(int)(map[i/5][i%5]=='H') );
        sign[i/5][i%5] = true;
    }
}
int main()
{
    int i, j;
    for( i=0; i<5; i++ )    
        scanf( "%s", map[i] );    
    for( i=0; i<5; i++ )
    for( j=0; j<5; j++ )
    {
        sign[i][j] = true;
        flag[i][j] = 0;
    }
    ans = 0;visit = 0;    
    search( -1, 0, 0, 0 );
    printf( "%dn", ans );
    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 *