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为无法遍历一次。

样例输入

15 4 0 0

样例输出

32

 1 #include "bits/stdc++.h" 2  3 using namespace std; 4 const int maxN = 210 ; 5 typedef long long QAQ ; 6  7 int N , M ; 8 bool vis[ maxN ][ maxN ] ; 9 bool limit[ maxN ][ maxN ] ;10 const int Next[ 8 ][ 2 ] = { { 1 , 2 } , { 2 , 1 } , { 2 , -1 } , { -1 , 2 } , { 1 , -2 } , { -2 , 1 } , { -2, -1 } , { -1 , -2 } } ;11 12 QAQ Ans = 0 ;13 14 void DFS( const int x , const int y , const int step ) {15         if( step == N * M ) {16                 ++Ans;17                 return;18         }19         else for ( int i=0 ; i<=7 ; ++i ) {20                 int xx = x + Next[ i ][ 0 ] ;21                 int yy = y + Next[ i ][ 1 ] ;22                 if ( xx >= 0 && yy >= 0 && xx < N && yy < M && !vis[ xx ][ yy ] ) {23                         vis[ xx ][ yy ] = true ;24                         DFS ( xx , yy , step + 1 ) ;25                         vis[ xx ][ yy ] = false ;26                 }27         }28 }29 30 void Init ( const int n , const int m ) {31         for ( int i=0 ; i<n ; ++i ) 32                 for ( int j=0 ; j<m ; ++j ) 33                         limit[ i ][ j ] = true ; 34 }35 36 int main ( ) {37         int start_x , start_y , T ; 38         scanf ( "%d" , &T ) ;39         while ( T-- ){40                 Ans = 0 ;41                 scanf ( "%d%d%d%d" , &N , &M , &start_x , &start_y ) ; 42                 //Init ( N , M ) ;43                 vis[ start_x ][ start_y ] = true ;44                 DFS ( start_x , start_y , 1 ) ;45                 memset ( vis , false , sizeof ( vis ) ) ;46                 memset ( limit , false , sizeof ( limit ) ) ;47                 cout << Ans << endl ;48         }49         return 0 ;50 }

View Code

 

2016-10-18 23:38:07