CF1214D

た入场券 2024-04-20 10:34 8阅读 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 条评论，8人围观）

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

相关阅读

相关 CF1214D

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

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

相关 CF1214C

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

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

相关 CF1214B

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

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

相关 CF1214A

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

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

相关 CF981D

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

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

相关 CF427D

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

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

相关【构造】CF1853D

[Problem - D - Codeforces][] 题意： ![567dd31617514d0d9a4685c313eb2cb8.png][] 思路： ![2a8

心已赠人/ 2024年03月23日 22:30/ 0 赞/ 22 阅读

相关【构造】CF1798 D

[Problem - D - Codeforces][] 题意： ![ee9f61a4f71440ea8d521c072445781b.png][] 思路：首先如果

超、凢脫俗/ 2024年03月23日 20:15/ 0 赞/ 2 阅读

相关【DFS】CF598D

[Problem - D - Codeforces][] 题意： ![cb608ca46bcd48db8fbf2f84cabd4ec3.png][] ![18dc491a

梦里梦外;/ 2024年03月22日 22:01/ 0 赞/ 22 阅读

相关 CF1110D Jongmah

题意给出\\(n\\)个在\\(1\\)到\\(m\\)范围内的数\\(a\_i\\)，定义一个三元组为\\((x,x,x)\\)或者\\((x,x+1,x+2)\\)

深藏阁楼爱情的钟/ 2022年01月12日 09:29/ 0 赞/ 139 阅读