题目背景(题目链接) 题目描述 给定一个NM方格的迷宫,迷宫里有T处障碍,障碍处不可通过。 在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。 给定起点坐标和终点坐标,每个方格最多经过一次,问有多少种从起点坐标到终点坐标的方案。 输入格式 第一行为三个正整数N,M,T,分别表示迷宫的长宽和障碍总数。 第二行为四个正整数SX,SY,FX,FY,SX,SY代表起点坐标,FX,FY代表终点坐标。 接下来$T$行,每行两个正整数,表示障碍点的坐标。 输出格式 输出从起点坐标到终点坐标的方案总数。 样例输入 &...
介绍 vector(矢量;向量),vector是C标准模板库(STL)中的部分内容,中文偶尔译作“容器”,但并不准确。它是一个多功能的,能够操作多种数据结构和算法的模板类和函数库。vector之所以被认为是一个容器,是因为它能够像容器一样存放各种类型的对象,简单地说,vector是一个能够存放任意类型的动态数组,能够增加和压缩数据。 vector是同一种类型的对象的集合,每个对象都有一个对应的整数索引值,它的一个容器中的所有对象都必须是同一种类型的。 vector是一个类模板。使用模板可以编写一个类定义或函数定义,而用于多个不同的数据类型。因此,我们可以定义保存string对象的v...
介绍 栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。 栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针...
定义 排列 排列,一般地,从n个不同元素中取出m(m≤n)个元素,按照一定的顺序排成一列,叫做从n个元素中取出m个元素的一个排列。特别地,当m=n时,这个排列被称作全排列。 用Αnm表示“从n个元素里取m个元素,排成一排的方案数”,也就是Αnm=n!/(n-m)! ,将它称为排列数。 注:n!即为n的阶乘,记作n!=n×(n-1)×…×2×1。例如3!=6,4!=24,5!=120…… 组合 组合是一个数学名词。一般地,从n个不同的元素中,任取m(m≤n)个元素为一组,叫作从n个不同元素中取出m个元素的一个组合。我们把有关求组合的个数的问题叫作组合问题。 用...
队列的概念 在说队列之前,先回忆一下栈是什么,我们一般说栈是一个先进后出的数据结构,而队列就是先进先出的数据结构。 队列是定在表的一端进行插入,表的另一端进行删除。 通常,我们称进数据的一端为队尾,出数据的一端为队首(这边需要注意,经常会记反起码我是这样的),数据元素进队列的过程称为入队,出队列的过程称为出队。 队列存储的方式主要分为两种: 1.顺序队列(集中存储) 2.链队列(分散存储) 两者的区别主要就是顺序表和链表的区别。 队列的用法 和栈一样,队列同样可以使用STL来操作。 队列的头文件是: 1incl...
前缀和 前缀和,顾名思义,就是所有前缀之和,给一个最基本的例子: 如图,a为原始数组,s为完成预处理后的数组,很容易看出来s[i]=s[i1]+a[i],而也就是s[i]=a[1]+a[2]+……+a[i],需要注意的是记s[0]=0。 那么,如果我想要知道一个区间的区间和该怎么做呢?其实很简单,例如要求区间35的区间和,就可以用s[5]-s[2]=19-8=11。这里同样需要注意当减去区间左边界时需要将其减1,及求lr的区间和,是用s[r]-s[l-1]。 根据以上求区间前缀和的思路可以完成以下代码 1include<bits/stdc.h>...
递归 引入 什么是递归?先看大家都熟悉的一个民间故事:从前有座山,山上有座庙,庙里有一个老和尚在给小和尚讲故事,故事里说,从前有座山,山上有座庙,庙里有一个老和尚在给小和尚讲故事,故事里说……。象这样,一个对象部分地由它自己组成,或者是按它自己定义,我们称之为递归。 一个函数、过程、概念或数学结构,如果在其定义或说明内部又直接或间接地出现有其本身的引用,则称它们是递归的或者是递归定义的。在程序设计中,过程或函数直接或者间接调用自己,就被称为递归调用。 递归的概念 递归过程是借助于一个递归工作栈来实现的 问题向一极推进,这一过程叫做递推; 问题逐一解决,最后回到...