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