世界名画陈列馆由 n×m 个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右 4 个陈列室。试设计一个安排警卫机器人哨位的算法，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，并且要求每一个陈列室仅受一个警卫机器人监视，且所用的警卫机器人数最少。用回溯法实现写出C语言代码

这是一个典型的图着色问题，可以使用回溯法来解决。具体步骤如下：

1. 构建一个图，每一个陈列室为一个节点，如果两个陈列室有公共墙壁，则它们之间有一条边。

2. 定义一个数组color，用来存储每个节点的颜色，初始值为0。

3. 从第一个节点开始，对每个节点进行如下操作：

1. 遍历该节点的所有邻居节点，如果邻居节点的颜色已经被染色且与当前节点颜色相同，则不能将当前节点染成该颜色，需要尝试其他颜色。

2. 如果当前节点可以被染成某种颜色，则将该颜色赋给color数组。

3. 递归调用下一个节点，重复以上操作。

4. 如果所有节点都被染色，则得到一个可行的方案，记录使用的警卫机器人数。

5. 回溯到上一个节点，尝试其他颜色，重复以上操作。

6. 直到所有节点的所有颜色都尝试完毕，得到最优解。

下面是完整的C语言代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_NODE 100 // 最大节点数

int graph[MAX_NODE][MAX_NODE]; // 图
int color[MAX_NODE]; // 节点颜色
int node_num; // 节点数
int robot_num = MAX_NODE; // 初始警卫机器人数

// 判断节点是否可以染成指定颜色
bool is_valid_color(int node, int c)
{
    for (int i = 0; i < node_num; i++) {
        if (graph[node][i] && c == color[i]) {
            return false;
        }
    }
    return true;
}

// 计算警卫机器人数量
int get_robot_num()
{
    int count = 0;
    for (int i = 0; i < node_num; i++) {
        if (color[i] > count) {
            count = color[i];
        }
    }
    return count;
}

// 回溯法染色
void backtrack(int node)
{
    if (node == node_num) {
        int robots = get_robot_num();
        if (robots < robot_num) {
            robot_num = robots;
        }
        return;
    }

    for (int i = 1; i <= robot_num; i++) {
        if (is_valid_color(node, i)) {
            color[node] = i;
            backtrack(node + 1);
            color[node] = 0; // 回溯
        }
    }
}

int main()
{
    int n, m;
    printf("请输入陈列室的行数和列数：");
    scanf("%d %d", &n, &m);
    node_num = n * m;

    printf("请输入相邻陈列室的信息（1为有公共墙壁，0为无）：\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int node = i * m + j;
            if (i > 0) {
                int neighbor = (i - 1) * m + j;
                graph[node][neighbor] = graph[neighbor][node] = 1;
            }
            if (j > 0) {
                int neighbor = i * m + j - 1;
                graph[node][neighbor] = graph[neighbor][node] = 1;
            }
            if (i < n - 1) {
                int neighbor = (i + 1) * m + j;
                graph[node][neighbor] = graph[neighbor][node] = 1;
            }
            if (j < m - 1) {
                int neighbor = i * m + j + 1;
                graph[node][neighbor] = graph[neighbor][node] = 1;
            }
        }
    }

    backtrack(0);

    printf("最少需要%d个警卫机器人\n", robot_num);

    return 0;
}