CodeForces - 1214D D. Treasure Island
2024-10-06 13:35:17
题目链接: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 ;
}
最新文章
- 现代3D图形编程学习-基础简介(1) (译)
- 30.编写一个Shape类,具有属性:周长和面积; 定义其子类三角形和矩形,分别具有求周长的方法。 定义主类E,在其main方法中创建三角形和矩形类的对象, 并赋给Shape类的对象a、b,使用对象a、b来测试其特性。
- 标准库函数atoi的实现
- [Python爬虫] 在Windows下安装PIP+Phantomjs+Selenium
- [LeetCode]题解(python):049-Groups Anagrams
- select resharper shortcuts scheme
- lightoj 1024 (高精度乘单精度)
- struts2 package元素
- USB-CSW之旅
- 第一章 andrid visdio 安装
- PHP数组关于数字键名的问题
- 多线程---静态同步函数的锁是class(转载)
- jquery 循环数组输出显示在html页面
- 项目实战12.2—企业级监控工具应用实战-zabbix操作进阶
- Unity3D学习笔记(五)C#与JavaScript组件访问的比较
- 从HTTL模板引擎看软件设计原则
- CRM中QueryDict和模型表知识补充
- scrapy 简单爬虫实验
- 【入门详解】MyBatis入门基础详解
- .NET Entity Framework (with Oracle ODP.NET)
热门文章
- Winform去掉标题栏后移动窗体
- ASP.NET Core 3.0 : 二十五. TagHelper
- 【linux】【jenkins】自动化部署一 安装jenkins及Jenkins工作目录迁移
- 快速整理代码(c#)
- 从壹开始学习NetCore 45 ║ 终于解决了事务问题
- go 学习笔记之10 分钟简要理解 go 语言闭包技术
- C/C++中变量的作用域和存储类型简介
- 如何安装PHPstorm并配置php运行环境运行php项
- python selenium模拟登陆qq空间
- 死磕 java线程系列之自己动手写一个线程池(续)