題面描述
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×m which is surrounded by the ocean. Let us number rows of the field with consecutive integers from 1 to n from top to bottom and columns with consecutive integers from 1 to m from left to right. Denote the cell in r-th row and c-th column as (r,c). Some of the island cells contain impassable forests, and some cells are free and passable. Treasure is hidden in cell (n,m).
Vasya got off the ship in cell (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) he can move only to cells (x+1,y) and (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) where Vasya got off his ship and (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.
輸入格式
First line of input contains two positive integers n, m (3≤n?m≤1000000), sizes of the island.
Following n lines contains strings si of length m describing the island, j-th character of string si equals "#" if cell (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), i.e. the first cell of the first row, and he wants to reach cell (n,m), i.e. the last cell of the last row.
It's guaranteed, that cells (1,1) and (n,m) are empty.
輸出格式
Print the only integer k, which is the minimum number of cells Evil Witch has to turn into impassable forest in order to prevent Vasya from reaching the treasure.
樣例數(shù)據(jù)
樣例輸入
2 2
..
..
樣例輸出
2
題解
簡單題......
事實上，考慮最大答案拯啦，就是將(1,2)和(2,1)一起堵上框仔，或者將(n-1,m)和(n,m-1)一起堵上垢揩，因此答案最大為2衬横。
再考慮走法菱阵。如果單純判斷是否能到達(dá)起點/終點的相鄰節(jié)點拯坟，可能會出現(xiàn)以下情況：
input:
. . . . . # .
. . . . . # .
. . . . . # .
. . . . . . .
# # # # # # .
. . . . . . .
這時我們發(fā)現(xiàn) 起點和終點的兩個臨近節(jié)點都能到達(dá)晤碘，而答案則是1衍锚，因此我們需要其它方案友题。
考慮是否有兩條通路。我們先進(jìn)行一次dfs戴质，若沒有通路則直接輸出0度宦。若有通路則將這條路徑堵上，并進(jìn)行第二次dfs告匠。若第二次dfs有答案則輸出2斗埂，否則輸出1。
關(guān)于正確性凫海，因為dfs的特性是不碰到障礙物就不會改變移動的方向（左手法則/右手法則）呛凶，因此即使有兩個解，我們也會優(yōu)先堵上不會對另外一個答案產(chǎn)生影響的通路行贪，可以保證正確漾稀。
#include<bits/stdc++.h>
#define int long long
#define maxn 1000
using namespace std;
inline char get(){
static char buf[30000],*p1=buf,*p2=buf;
return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
register char c=getchar();register int f=1,_=0;
while(c>'9' || c<'0')f=(c=='-')?-1:1,c=getchar();
while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=getchar();
return _*f;
}
int n,m;
set<pair<int,int> > mp,vis;
int dfs(int x,int y){
//cout<<x<<" "<<y<<endl;
if(x==n && y==m)return 1;
if(vis.count(make_pair(x,y)))return 0;
if(mp.count(make_pair(x,y)))return 0;
if(x>n || y>m)return 0;
vis.insert(make_pair(x,y));
if(dfs(x+1,y)==1){
mp.insert(make_pair(x+1,y));
return 1;
}
if(dfs(x,y+1)==1){
mp.insert(make_pair(x,y+1));
return 1;
}
return 0;
}
signed main(){
//freopen("1.txt","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(register int i=1;i<=n;i++){
char cas;
for(register int j=1;j<=m;j++){
cin>>cas;
if(cas=='#')mp.insert(make_pair(i,j));
}
}
if(dfs(1,1)==0){
cout<<0;
return 0;
}
vis.clear();
if(dfs(1,1)==0){
cout<<1;
return 0;
}
else{
cout<<2;
return 0;
}
return 0;
}
