8465  马走日

描述

马在中国象棋以日字形规则移动。

请编写一段程序，给定n*m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

输入

第一行为整数T(T < 10)，表示测试数据组数。
每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0<=x<=n-1,0<=y<=m-1, m < 10, n < 10)

输出

每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。

样例输入

1

5 4 0 0

样例输出

32

 #include "bits/stdc++.h"

 using namespace std;

 const int maxN =  ;

 typedef long long QAQ ;

 int N , M ;

 bool vis[ maxN ][ maxN ] ;

 bool limit[ maxN ][ maxN ] ;

 const int Next[  ][  ] = { {  ,  } , {  ,  } , {  , - } , { - ,  } , {  , - } , { - ,  } , { -, - } , { - , - } } ;

 QAQ Ans =  ;

 void DFS( const int x , const int y , const int step ) {

         if( step == N * M ) {

                 ++Ans;

                 return;

         }

         else for ( int i= ; i<= ; ++i ) {

                 int xx = x + Next[ i ][  ] ;

                 int yy = y + Next[ i ][  ] ;

                 if ( xx >=  && yy >=  && xx < N && yy < M && !vis[ xx ][ yy ] ) {

                         vis[ xx ][ yy ] = true ;

                         DFS ( xx , yy , step +  ) ;

                         vis[ xx ][ yy ] = false ;

                 }

         }

 }

 void Init ( const int n , const int m ) {

         for ( int i= ; i<n ; ++i )

                 for ( int j= ; j<m ; ++j )

                         limit[ i ][ j ] = true ;

 }

 int main ( ) {

         int start_x , start_y , T ;

         scanf ( "%d" , &T ) ;

         while ( T-- ){

                 Ans =  ;

                 scanf ( "%d%d%d%d" , &N , &M , &start_x , &start_y ) ;

                 //Init ( N , M ) ;

                 vis[ start_x ][ start_y ] = true ;

                 DFS ( start_x , start_y ,  ) ;

                 memset ( vis , false , sizeof ( vis ) ) ;

                 memset ( limit , false , sizeof ( limit ) ) ;

                 cout << Ans << endl ;

         }

         return  ;

 }

2016-10-18 23:38:07