NOIP2009普及组初赛 完善程序 第2题《国王放置》

DFS

#include <cstring>
#include <iostream>

using namespace std;

const int N = 20;

int n, m, k, ans;
int hash[N][N];

void work(int x, int y, int tot)
{
    int i, j;
    if (tot == k)  //递归边界 
    {
        ans++;
        return;
    }

    do
    {
        while (hash[x][y])  //当hash[x][y]为0的时候找到一个可用位置 
        {
            y++;
            if (y == m)  //换行操作 
            {
                x++, y = 0;  //1空 
            }
            if (x == n)
                return;
        }

        //printf("----%d %d\n", x, y);

        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)
                        hash[i][j] += 1;   //2空  
        //以x,y为中心，9个位置，分别攻击一次 

        work(x, y, tot + 1 );  //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)
                        hash[i][j] -= 1;   //恢复现场   //4空 

        y++; //寻找下一个点，默认是右边的点
        if (y == m) 
        {
            x++, y = 0;
        } 
        if (x == n)
            return;
    }while (1);    //do-while    

}

int main()
{
    cin >> n >> m >> k;
    ans = 0;
    memset(hash, 0, sizeof hash);

    work(0, 0, 0);  //5空 

    cout << ans << endl;

    return 0;
}

分析：

DFS的题目，真的是很难去模拟输出中间的过程，栈的情况，没办法用cout大法完美的展现出来。

这道题目hash[i][j]，存放的是一个位置被攻击的次数，而不是true false，因为一个位置可能被攻击多次，或者在恢复现场的时候，被撤回好几次。用true false的开关，会造成不准确。当找到一个点，就以这个点为中心，总共9个位置，都攻击一遍，让下一个点，不能在这9个位置里再选了。

if (y == m) 
{
      x++, y = 0;
} 

这个是回行的一个技巧

当找到一个放置国王的位置，放置成功后，下一个位置是遍历当前点右边的那个点。就是y++（同一行，下一列）