Luogu [P1958] 上学路线_NOI导刊2009普及(6)
2024-08-27 03:38:21
上学路线_NOI导刊2009普及(6)
题目详见:上学路线_NOI导刊2009普及(6)
这是一道基础的DFS(深搜)题,堪称模板,是新手练习搜索与回溯的好题选。
大致思路:从(1,1)开始搜索,每次只能往上走或往右走一个格(遇到题目给出的障碍物则直接不走),一直到(a,b),再回来找另一条路。每到一遍(a,b)就让计数器tot+1,最后输出tot,即为最终方案总数。
AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int k,a,b,f[][],tot;
void search(int x,int y)
{
if(x==a&&y==b)
{
tot++;
return;
}
if((x+<=a)&&f[x+][y]==)//往上找
search(x+,y);
if((y+<=b)&&f[x][y+]==)//往右找
search(x,y+);
}
int main()
{
cin>>a>>b>>k;
for(int i=;i<=k;i++)
{
int x,y;
cin>>x>>y;
f[x][y]=;
}
search(,);
cout<<tot;
return ;
}
最新文章
- 轻量的、可自定义 CSS 的 Lightbox 相册插件
- centos ADSL 拨号上网设置
- 解读Unity中的CG编写Shader系列三
- JS&;CSS文件请求合并及压缩处理研究(三)
- 使用jenkins构建持续集成平台
- 线性空间光照(即Gamma)
- js&;jq 发送验证码倒计时
- FDATool使用
- -g vs -rdynamic
- 跨平台的目录遍历实现方法(windows和linux已经测试)
- 移动端meta标签整理-备
- IFE-20 笔记
- Akka(12): 分布式运算:Cluster-Singleton-让运算在集群节点中自动转移
- ●SPOJ 8222 NSUBSTR - Substrings(后缀数组)
- 转载一篇好理解的vue ssr文章
- 编程经验点滴----巧妙解决 Oracle NClob 读写问题
- isScroll 插件在iPhone 5s 和以上版本
- :复合模式:duck
- java 开发微信中回调验证一直提示 解密失败处理(Java)
- H5实现页面内跳转页面