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; }