题目链接:https://vjudge.net/problem/2728294/origin

思路:可以抽象成管道,先试试能不能找到一个通道能通到终点,

如果可以则封锁这个通道,一个石头即可,

再试试能不能找到另一个通道能到达终点,

如果可以则再用一个石头封锁这个通道。

整个题目抽象成能不能找出两个独立的通道(如果不能说明需要公用一个管道),从起点流到终点。

为了充分利用格子,最合理化找出通道,应该选择靠边的方法找格子。

#include <stdio.h>
#include <iostream>
using namespace std; const int N = (int)1e6+;
char mp[N];
int vis[N];
int n,m; inline bool check(int x,int y){
return x>=&&x<n&&y>=&&y<m;
} bool dfs(int x,int y){ if( !check(x,y) || vis[x*m+y] ) return false;
if( x*m+y == n*m- ) return true;
vis[x*m+y] = ; return dfs(x,y+) || dfs(x+,y);
} int main(){ scanf("%d%d",&n,&m); for(int i = ; i < n; i++){
scanf("%s",mp+i*m);
for(int j = i*m; j < (i+)*m; j++){ if(mp[j] == '#') vis[j] = ;
}
} bool flag = ;
for(int o = ; o <= ; o++){ vis[] = ;
if(!dfs(,)){
cout << o << endl;
flag = ;
break;
}
}
if(flag) cout << << endl; return ;
}

最新文章

  1. 现代3D图形编程学习-基础简介(1) (译)
  2. 30.编写一个Shape类,具有属性:周长和面积; 定义其子类三角形和矩形,分别具有求周长的方法。 定义主类E,在其main方法中创建三角形和矩形类的对象, 并赋给Shape类的对象a、b,使用对象a、b来测试其特性。
  3. 标准库函数atoi的实现
  4. [Python爬虫] 在Windows下安装PIP+Phantomjs+Selenium
  5. [LeetCode]题解(python):049-Groups Anagrams
  6. select resharper shortcuts scheme
  7. lightoj 1024 (高精度乘单精度)
  8. struts2 package元素
  9. USB-CSW之旅
  10. 第一章 andrid visdio 安装
  11. PHP数组关于数字键名的问题
  12. 多线程---静态同步函数的锁是class(转载)
  13. jquery 循环数组输出显示在html页面
  14. 项目实战12.2—企业级监控工具应用实战-zabbix操作进阶
  15. Unity3D学习笔记(五)C#与JavaScript组件访问的比较
  16. 从HTTL模板引擎看软件设计原则
  17. CRM中QueryDict和模型表知识补充
  18. scrapy 简单爬虫实验
  19. 【入门详解】MyBatis入门基础详解
  20. .NET Entity Framework (with Oracle ODP.NET)

热门文章

  1. Winform去掉标题栏后移动窗体
  2. ASP.NET Core 3.0 : 二十五. TagHelper
  3. 【linux】【jenkins】自动化部署一 安装jenkins及Jenkins工作目录迁移
  4. 快速整理代码(c#)
  5. 从壹开始学习NetCore 45 ║ 终于解决了事务问题
  6. go 学习笔记之10 分钟简要理解 go 语言闭包技术
  7. C/C++中变量的作用域和存储类型简介
  8. 如何安装PHPstorm并配置php运行环境运行php项
  9. python selenium模拟登陆qq空间
  10. 死磕 java线程系列之自己动手写一个线程池(续)