G - 말 걷는 날

1772 단어 검색 학습
말은 중국 장기에서 일자형 규칙으로 이동한다.
n*m 크기의 바둑판과 말의 초기 위치(x, y)를 정하는 프로그램을 작성해 주십시오. 바둑판의 같은 점을 반복해서 통과할 수 없도록 요구하고 말이 바둑판의 모든 점을 얼마나 많이 범람할 수 있는지 계산하십시오.
Input
첫 번째 동작 정수 T(T < 10)는 테스트 데이터 그룹 수를 나타냅니다.각 그룹의 테스트 데이터는 네 개의 정수로 한 줄을 포함하는데 각각 바둑판의 크기와 초기 위치 좌표 n, m, x, y이다.(0<=x<=n-1,0<=y<=m-1, m < 10, n < 10)
Output
각 그룹의 테스트 데이터는 한 줄을 포함하고 하나의 정수로 말이 바둑판을 누를 수 있는 경로의 총수를 나타낸다. 0은 한 번 누를 수 없는 것이다.
Sample Input
1
5 4 0 0

Sample Output
32

문제를 깊이 파고드는 것은 본보기를 깊이 파고든 것과 같다.
#include #include #include #include #include #include #include #include using namespace std; #define inf 0x3f3f3f3f; int n,m,stx,sty,ans; int book[100][100]; int dis[8][2]={{1,2},{2,1},{-1,2},{-2,1},{-1,-2},{-2,-1},{1,-2},{2,-1}}; bool check() {     int sum=0;     for(int i=0;i     {         for(int j=0;j         {             if(book[i][j])                 sum++;         }
    }     if(sum==n*m)         return 1;     else         return 0; } void cn(int x,int y) {     if(check()==1)     {         ans++;         return ;     }     else     {         for(int i=0;i<8;i++)         {             int tx=x+dis[i][0];             int ty=y+dis[i][1];             if(tx<0||tx>=n||ty<0||ty>=m||book[tx][ty]==1)             {                 continue;             }             book[tx][ty]=1;             cn(tx,ty);             book[tx][ty]=0;         }     }     return ; } int main() {     int t;     scanf("%d",&t);     while(t--)     {         memset(book,0,sizeof(book));         scanf("%d%d%d%d",&n,&m,&stx,&sty);         book[stx][sty]=1;         ans=0;         cn(stx,sty);         printf("%d",ans);
    }     return 0; }

좋은 웹페이지 즐겨찾기