问题分析

本题要求根据给定的三个影子图案，判断是否能够通过将单位立方体沿着它们的面粘合在一起，构造出一个能够投射出这些影子的单件实体。输入的每个数据集包含一个维度值和三个影子图案，每个图案由 n 行，每行 n 个字符组成，其中 “X” 表示影子，“-” 表示光线可以穿过的地方。

方法思路

读取输入：首先读取每个数据集的维度值 n，然后读取三个影子图案，每个图案由 n 行字符串组成。 验证边缘条件：检查每个图案的边缘是否至少有一个 “X”，如果不满足，则该数据集无效。 构造三维数组：将每个图案看作一个二维数组，然后将三个图案组合成一个三维数组，其中第三维表示不同的图案。 填充三维数组：对于每个图案中的 “X” 位置，在三维数组中相应的位置设置为 1，表示有立方体存在。 检查一致性：遍历三维数组，检查每个位置是否满足所有图案的要求。如果某个位置在一个图案中是 “X”，但在其他图案中没有对应的立方体，则该数据集无效。 输出结果：如果所有位置都满足要求，则输出 “Valid set of patterns”，否则输出 “Impossible combination”。

代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define INF 0xfffffff
#define MAXN 105
 
int d[MAXN];
int w[MAXN][MAXN];
int v[MAXN];
int n;
 
void dj(int s){
	memset(v, 0, sizeof(v));
	for(int i = 0; i < n; i++)
		d[i] = ( i == s ? 0 : INF );
	for(int i = 0; i < n; i++){
		int x, m = INF;
		for(int y = 0; y < n; y++)
			if( !v[y] && d[y] <= m )
				m = d[x=y];
		v[x] = 1;
		for(int y = 0; y < n; y++)
			if( w[x][y] != -1 && d[y] > d[x] + w[x][y])
				d[y] = d[x] + w[x][y];
	}
}
 
int s2i(char* str){
	if (str[0] == 'x') return -1;
	int ret = 0;
	while (*str)
		ret = ret * 10 + (*str++) - '0';
	return ret;
}
 
int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			w[i][j] = -1;
	char input[40];
	for(int i = 0; i < n; i++){
		w[i][i] = 0;
		for(int j = 0; j < i; j++){
			scanf("%s", input);
			w[i][j] = w[j][i] = s2i(input);
		}
	}
 
	dj(0);
 
	int output = -1;
	for(int i = 1; i < n; i++)
		if( d[i] > output ) output = d[i];
	printf("%d\n", output);
	return 0;
}