CF1214D

た入场券 2024-04-20 10:34 96阅读 0赞

##  ##

CF1214D

### 题意： ###

> 给你一个 $ n \\times m $ 的矩阵，求最少用多少个障碍，将 $ (1,1) $ 到 $ (n,m) $ 的路径堵死。

### 题意： ###

> 因为可以将起点两边堵死，所以答案最多是 $ 2 $ ，所以答案就只有 $ 0,1,2 $ 。  
> 先两遍DFS抠出既能从 $ (1,1) $ 到达又能到达 $ (n,m) $ 的点，看看每个步数内能到达的点是否只有一个。

### CODE: ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long #define N 1000010 int n,m,s,ans,f; bool vis[N]; char ch[N]; void dfs(int x) { if(ans) return; if(x == f) { ans++; return; } int l = x / m,r = x % m; if(l + 1 < n && vis[(l + 1) * m + r] == 0 && ch[(l + 1) * m + r] != '#') { vis[(l + 1) * m + r] = 1; dfs((l + 1) * m + r); } if(ans) return; if(r + 1 < m && vis[l * m + r + 1] == 0 && ch[l * m + r + 1] != '#') { vis[l * m + r + 1] = 1; dfs(l * m + r + 1); } } int main() { scanf("%d%d",&n,&m); for(int i = 0 ; i < n ; i++) scanf("%s",ch + i * m); f = n * m - 1,ans = 0; vis[s] = 1,vis[f] = 0; dfs(s); if(ans == 0) { puts("0"); return 0; } vis[s] = 1,vis[f] = 0; ans = 0; dfs(s); if(ans == 0) puts("1"); else puts("2"); //system( return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11469851.html

发表评论取消回复

表情：

评论列表（有 0 条评论，96人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1214D

CF1214D 题意： > 给你一个 $ n \\times m $ 的矩阵，求最少用多少个障碍，将 $ (1,1) $ 到 $ (n,m) $ 的路径堵死...

た入场券/ 2024年04月20日 10:34/ 0 赞/ 97 阅读

相关 CF1214C

CF1214C 题意： > 给你一个括号序列，问你时候能仅移动相邻的两个元素，使括号序列合法。解法： > 可以先考虑普通括号序列怎么做 > 这...

亦凉/ 2024年04月20日 10:33/ 0 赞/ 91 阅读

相关 CF1214B

CF1214B 解法： > 暴力枚举，时间复杂度 $ O(n) $ CODE: include<iostream> include<cstd...

不念不忘少年蓝@/ 2024年04月20日 10:33/ 0 赞/ 98 阅读

相关 CF1214A

CF1214A 题意： > 有n个卢布，要换成美元和欧元，使手上剩余的卢布最少。一美元价值d卢布，一欧元价值e卢布。解法： > 可以看成只有两个没...

「爱情、让人受尽委屈。」/ 2024年04月20日 10:32/ 0 赞/ 92 阅读

相关 CF981D

CF981D 题意： > 给你n个数，要求你分成k堆。每堆的内部加和，每堆之间是相与。问最大的值。解法： > 二进制下最大的数的所有位一定是1，所...

缺乏、安全感/ 2024年04月20日 10:26/ 0 赞/ 88 阅读

相关 CF427D

CF427D > SA的奇技淫巧，其实就是板子。题意： > 给定两个字符串，求最短的满足各只出现一次的连续公共字串解析： > 一般情况下，SA...

素颜马尾好姑娘i/ 2024年04月20日 10:25/ 0 赞/ 89 阅读

相关 CF1208D

CF1208D 题意； > 给你一个数组，要求支持单点修改和单点查询解法： > 直接线段树搞一搞就没了。 CODE： includ...

系统管理员/ 2024年04月20日 10:24/ 0 赞/ 97 阅读

相关构造——cf1214E

首先定义三元组（2\i-1,2\i,d），将n个三元组按d降序排列，然后取每个三元组的2\i-1连在一起，构成一条长为n-1的链然后降序枚举每个三元组，把对应的2\i在链上

深藏阁楼爱情的钟/ 2023年10月11日 09:04/ 0 赞/ 30 阅读

相关网格图必经点+dfs——cf1214D

先正着走一次把所有可行路径标记出来，然后倒着走两条路径，一条是能向下就向下的路径，另一条能向右就向右。如果这两条路径相交，那么(1,1)-(n,m)路径上比有个必经点，把这

不念不忘少年蓝@/ 2023年10月11日 07:49/ 0 赞/ 33 阅读

相关 CodeForces1214D

[CodeForces1214D][] 这个题据我所知有两种比较优秀的做法. 第一种是\\(DP\\)统计每个点的路径数,然后找出必经点,再从必经点开始\\(bfs\\

柔光的暖阳◎/ 2023年06月02日 11:58/ 0 赞/ 31 阅读