All of us love treasures, right? That's why young Vasya is heading for a Treasure Island.

Treasure Island may be represented as a rectangular table n×mn×m which is surrounded by the ocean. Let us number rows of the field with consecutive integers from 11 to nn from top to bottom and columns with consecutive integers from 11 to mm from left to right. Denote the cell in rr-th row and cc-th column as (r,c)(r,c). Some of the island cells contain impassable forests, and some cells are free and passable. Treasure is hidden in cell (n,m)(n,m).

Vasya got off the ship in cell (1,1)(1,1). Now he wants to reach the treasure. He is hurrying up, so he can move only from cell to the cell in next row (downwards) or next column (rightwards), i.e. from cell (x,y)(x,y) he can move only to cells (x+1,y)(x+1,y) and (x,y+1)(x,y+1). Of course Vasya can't move through cells with impassable forests.

Evil Witch is aware of Vasya's journey and she is going to prevent him from reaching the treasure. Before Vasya's first move she is able to grow using her evil magic impassable forests in previously free cells. Witch is able to grow a forest in any number of any free cells except cells (1,1)(1,1) where Vasya got off his ship and (n,m)(n,m) where the treasure is hidden.

Help Evil Witch by finding out the minimum number of cells she has to turn into impassable forests so that Vasya is no longer able to reach the treasure.

Input

First line of input contains two positive integers nn, mm (3≤n⋅m≤10000003≤n⋅m≤1000000), sizes of the island.

Following nn lines contains strings sisi of length mm describing the island, jj-th character of string sisi equals "#" if cell (i,j)(i,j) contains an impassable forest and "." if the cell is free and passable. Let us remind you that Vasya gets of his ship at the cell (1,1)(1,1), i.e. the first cell of the first row, and he wants to reach cell (n,m)(n,m), i.e. the last cell of the last row.

It's guaranteed, that cells (1,1)(1,1) and (n,m)(n,m) are empty.

Output

Print the only integer kk, which is the minimum number of cells Evil Witch has to turn into impassable forest in order to prevent Vasya from reaching the treasure.

Examples
input

Copy
2 2
..
..
output

Copy
2
input

Copy
4 4
....
#.#.
....
.#..
output

Copy
1
input

Copy
3 4
....
.##.
....
output

Copy
2
Note

The following picture illustrates the island in the third example. Blue arrows show possible paths Vasya may use to go from (1,1)(1,1) to (n,m)(n,m). Red illustrates one possible set of cells for the Witch to turn into impassable forest to make Vasya's trip from (1,1)(1,1) to (n,m)(n,m) impossible.

题目大意: 起点是(1,1),,,终点(n,m),只能向下走或者向右走 ,#不能走,女巫可以将一个点变成#。问最少需要将几个点变成#才能使其不能到达终点(n,m)。

题解:先跑一边dfs,如果不可以到达的话,输出0,即不能到达,如果可以到达,把路径标记一下。然后再跑一遍dfs,如果可以不到达的话,输出1,输出2;

存图:  题目中给的数据范围是n*m<1e6 二维数组肯定不行。由于n*m所以我们开一个1e6的一维数组,然后没m个存一次,一共存m次

dfs版AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1E6+;
int d[][]={,,,};
int n,m;
char mp[N];
bool mark[N];
bool flag= false ;
void dfs(int id){
if(flag) return ;
if(id== n*m-){
flag =true;
return ;
}
else {
int x=id%m;//列
int y=id/m;//行
for(int i=;i<;i++){
int dx=y+d[i][];
int dy=x+d[i][];
if(dx>=n||dy>=m||mark[dx*m+dy]) continue ;
mark[dx*m+dy]=;
dfs(dx*m+dy);
if(flag) return ;
}
}
return ;
} int main(){
cin>>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]=='#') mark[j]=;
}
}
int i;
for(i=;i<=;i++){
mark[]=;
mark[n*m-] =;
flag= false ;
dfs();
if(!flag){
cout<<i<<endl;
break;
}
}
if(flag) puts("");
return ;
}

最新文章

  1. GDB调试32位汇编堆栈分析
  2. wsdl地址如何在远程服务器上查看源码?
  3. C# WinForm程序添加引用后调用静态方法时报“Interfaces_Helper.Global”的类型初始值设定项引发异常。---&gt; System.NullReferenceException: 未将对象引用设置到对象的实例。
  4. Flask+mongodb 实现简易个人博客
  5. URAL1355. Bald Spot Revisited
  6. wap测试学习
  7. bzoj3172
  8. POJ 1159 回文LCS滚动数组优化
  9. 小程序的get和post请求头的区别
  10. zTree节点重叠或者遮挡
  11. Linux(一)—— Unix&amp;Linux 历史
  12. sticky
  13. TableExport导出失败问题
  14. ubuntu中的环境变量
  15. CRM 2016 升级CRM365之注意事项
  16. 3.2Python的循环结构语句:
  17. jqGrid 列内容超过一定长度省略表示
  18. MySQL中datetime和timestamp的区别及使用
  19. HDU 5391Z ball in Tina Town 数论
  20. 区间DP--凸多边形三角剖分

热门文章

  1. 安装sql server 2005时出现“安装汇编”错误的解决办法
  2. MySQL 教程--检视阅读
  3. java-TreeMap
  4. 李宏毅老师机器学习课程笔记_ML Lecture 2: Where does the error come from?
  5. 刷oj之类的题时java Scanner读取太慢解决之道
  6. Mybatis详解系列(一)--持久层框架解决了什么及如何使用Mybatis
  7. 为何Keras中的CNN是有问题的,如何修复它们?
  8. WePY的开发环境的安装
  9. 深入理解NIO(二)—— Tomcat中对NIO的应用
  10. 算法(algorithm)