(国王放置) 在n*m的棋盘上放置k个国王,要求k个国王互相不攻击,有多少种不同的放置方法。假设国王放置在第(x,y)格,国王的攻击的区域是:(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。读入三个数n,m,k,输出答案。题目利用回溯法求解。棋盘行标号为0~n-1,列标号为0~m-1。#include <stdio.h>
#include <string.h> int n, m, k, ans; int hash[5][5]; void work(int x, int y, int tot) { int i, j; if (tot == k) { ans++; return; } do { while (hash[x][y]) { y++; if (y == m) { x++; y = 1; } if (x == n) return; } for (i = x - 1; i <= x + 1; i++) if (i >= 0 && i < n) for (j = y - 1; j <= y + 1; j++) if (j >= 0 && j < m) 2; 3; for (i = x - 1; i <= x + 1; i++) if (i >= 0 && i < n) for (j = y - 1; j <= y + 1; j++) if (j >= 0 && j < m) 4; y++; if (y == m) { x++; y = 0; } if (x == n) return; } while (1); } int main( ) { scanf("%d%d%d", &n, &m, &k); ans = 0; memset(hash, 0, sizeof(hash)); 5; printf("%d\n", ans); return 0; }