zzuli 1894 (985的方格难题)

2024-08-21 19:18
文章标签 难题 方格 985 zzuli 1894

本文主要是介绍zzuli 1894 (985的方格难题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

   dp   985的方格难题

Description

985走入了一个n * n的方格地图,他已经知道其中有一个格子是坏的。现在他要从(1, 1)走到(n, n),每次只可以向下或者向右走一步,问他能否到达(n,n)。若不能到达输出-1,反之输出到达(n,n)的方案数。

Input

第一行输入一个整数t,代表有t组测试数据。
每组数据第一行输入三个整数n,x,y,分别代表方格地图的大小以及坏掉格子的位置。
注:1 <= t <= 20,1 <= n <= 30,1 <= x,y <= n。

Output

若可以到达(n,n)则输出方案数对1e9 + 7取余的结果,反之输出-1。

Sample Input

2
2 1 2
2 2 2 

Sample Output

1
-1
题解:既然结果要对1e9取余,数据大肯定不能用DFS,会TLE。

用dp,map[i][j]代表到(i,j)处的方案数,需要注意的是i==1和j==1时的情况

#include<cstdio>
#include<cstring>
using namespace std;int main(){int t,n,i,j,x,y;int map[33][33];scanf ("%d",&t);while (t--){memset(map,1,sizeof(map));scanf ("%d %d %d",&n,&x,&y);for (i=1;i<=n;i++){for (j=1;j<=n;j++){if (i==x&&j==y)map[i][j]=0;else{if (i==1){if (j==1)map[i][j]=1;elsemap[i][j]=map[i][j-1];}else if (j==1)map[i][j]=map[i-1][j];elsemap[i][j]=(map[i-1][j]+map[i][j-1])%1000000007;}}}printf ("%d\n",map[n][n]==0?-1:map[n][n]);}return 0;
} 



这篇关于zzuli 1894 (985的方格难题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1094042

相关文章

接口自动化三大经典难题

目录 一、接口项目不生成token怎么解决关联问题 1. Session机制 2. 基于IP或设备ID的绑定 3. 使用OAuth或第三方认证 4. 利用隐式传递的参数 5. 基于时间戳的签名验证 二、接口测试中网络问题导致无法通过怎么办 1. 重试机制 2. 设置超时时间 3. 使用模拟数据 4. 网络问题的预检测 5. 日志记录与错误分析 6. 切换网络环境 7.

NYOJ 745 蚂蚁的难题(二)

OJ题目 : http://acm.nyist.net/JudgeOnline/problem.php?pid=745 描述 下雨了,下雨了,蚂蚁搬家了。 已知有n种食材需要搬走,这些食材从1到n依次排成了一个圈。小蚂蚁对每种食材都有一个喜爱程度值Vi,当然,如果Vi小于0的时候,表示蚂蚁讨厌这种食材。因为马上就要下雨了,所以蚂蚁只能搬一次,但是能够搬走连续一段的食材。时间紧急,你快帮

蓝桥杯第八届 方格分割(dfs)

标题:方格分割6x6的方格,沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。如图:p1.png, p2.png, p3.png 就是可行的分割法。试计算:包括这3种分法在内,一共有多少种不同的分割方法。注意:旋转对称的属于同一种分割法。请提交该整数,不要填写任何多余的内容或说明文字。   观察可得他是一个中心对称图形,我们只需要搜索它的对称线即可。我们可以把对称线抽象为从(

渣土车识别算法解决城市治理难题

随着城市化进程的加速,渣土车作为建筑工程中不可或缺的运输工具,其频繁的穿行和装载运输过程往往引发一系列问题,如超载、扬尘污染、乱倒渣土等,对城市环境和交通秩序造成了不良影响。为了解决这些问题,采用基于视觉分析的渣土车识别算法已成为现代城市治理中一种有效的技术手段。本文将从背景、技术实现、功能优势和应用方式等多个方面,探讨如何利用视觉分析技术来识别和管理渣土车,从而实现智能化、精细化的城市管理。

智能电话机器人电销- 完美解决企业营销扩展难题

在互联网时代,企业营销已经离不开数字化转型。智能电话机器人电销作为数字化营销的一种方式,受到越来越多企业青睐。那么,什么是智能电话机器人电销?为什么它能够解决企业营销扩展难题?本文将从多个方面进行解读,并分析其商业价值与应用前景。 什么是智能电话机器人电销? 智能电话机器人电销是利用人工智能技术,通过电话呼叫并与潜在客户进行对话,收集信息、建立客户档案、进行客户分类和筛选等一系列营销行为的方式

Xinstall助力App运营,下载唤起不再是难题!

在App推广和运营的道路上,你是否遇到过这样的困扰:用户点击下载链接后,却无法直接唤起App,导致用户体验不佳,甚至造成用户流失?别担心,今天我们就来科普一个神器——Xinstall,它能帮助你轻松解决App下载唤起的痛点,提升用户转化率和活跃度! 首先,让我们来了解一下什么是下载唤起App。简单来说,就是用户通过点击链接或扫描二维码等方式,能够直接下载并唤起指定的App。这在App推广和运营

传输大咖37 | 教育培训行业文件传输难题及解决方案

教育培训行业在文件传输过程中面临着一系列挑战,这些挑战不仅影响了工作效率,也对数据安全构成了潜在威胁。本文将探讨教育培训行业在文件传输方面的痛点,并提出镭速传输系统作为解决方案。 教育培训行业文件传输的痛点 信息孤岛问题:教育机构内部不同部门或校区间信息共享困难,导致资源无法有效利用。 数据安全风险:存储有大量敏感数据,如学生个人信息、成绩等,一旦泄露后果严重。 法规遵从性:需严格

选刊风向标!985大学近十年发文热门IEEE期刊盘点

本期盘点同济大学近十年有关IEEE旗下发文较多的期刊,一起来看看哪些是双一流大学热门发文期刊: 1、IEEE Transactions on Cybernetics • 影响因子:9.4 • JCR1区,中科院1区-Top • 检索数据库:SCIE • 期刊分区:JCR1区 中科院大类:计算机科学1区 中科院小类:自动化与控制系统1区;计算机:人工智能1区;计算机:控制论1区

3个高效免费的文件恢复助手,数据恢复不再是难题

PC Inspector File Recovery PC Inspector File Recovery是一款功能强大的数据恢复软件,适用于Windows操作系统。该软件能够恢复磁盘、软盘、可移动磁盘等存储设备上的数据,支持多种文件系统,包括FAT12、FAT16、FAT32和NTFS。它不仅可以恢复因错误删除、快速格式化、系统崩溃或病毒感染等原因丢失的文件,还能在引导区或FAT被删除

苹果备忘录误删了怎么恢复?靠谱攻略在这里,一文解决难题!

在使用苹果手机时,备忘录作为我们记录重要信息、待办事项和灵感闪现的得力助手,一旦不慎误删,往往令我们陷入困扰。苹果备忘录误删了怎么恢复?特别是面对没有及时备份或备份已过期的情况,恢复工作似乎变得更加棘手。 但别担心,本文将为你提供一份详尽而靠谱的攻略,助你轻松找回那些珍贵的备忘录。 苹果备忘录常见问题分析 我们在使用苹果备忘录时确实会遇到一些问题,有时会让我们不知所措。下面小编给大家