CSP真题 2015年3月 画图（基于BFS的CSP考题应用）

文章结构概览

• 总体说明

  • 问题概览

  • • 原始题目说明
    • 输入内容
    • 输出结果
    • 输入输出示例

  • 问题重新表述

  • 解题策略

  • • 策略简述

  • 归纳分析

  • 题目实现代码（c++）

总述

题目概述

BFS作为一种基础且较为简单的算法，在处理图论问题以及某些多维空间相关问题时，因其实现过程相对简便，因而常被应用于各类程序设计题目中。当针对某一问题设计出BFS或与其类似的DFS算法后，只要能够验证该算法在时间与空间复杂度方面均符合要求，即可直接进行实现。若在实际应用过程中发现部分数据无法满足条件，并且暂时没有其他可行的解决方案，也可将其作为获取部分分数的一种策略，在CSP中加以采用。

原题描述

问题描述
利用 ASCII 字符进行绘图是一项充满趣味性的活动，并由此发展出一种被称为 ASCII Art 的艺术形式。
本题需要编写一个程序，实现基于 ASCII 字符的绘图功能，支持以下两种操作：
1、绘制线条：提供两个端点的坐标信息，生成连接这两个端点的线段。为简化问题，题目中保证所有需要绘制的线段均为水平或垂直方向。水平方向的线段使用字符 - 进行绘制，垂直方向的线段则采用字符 | 表示。当一条水平线段与一条垂直线段在某一点交汇时，该交汇点将使用字符