2482 - F
小鑫有一天突然想去漂流，他来到一个既有小河又有土地的小岛上。他开始时站在岛的北面，还未上岛。现在他想要从岛的北面漂流到岛的南面去，由于有些地方可能被土地拦住，导致他无法直接顺着小河漂流到南面去。但小鑫有特殊的技巧，他可以挖穿土地，这样就可以顺利的漂到南面去了。小鑫又很懒，他想尽可能少的挖土，现在请问，他最少需要挖多少块土才能从岛的北面到南面去。
Input
第一行n， m，分别代表小岛的行数和列数
一个n*m的矩阵，0代表这个地方是小河，1代表是土地。
(1<=n,m<=10)
Output
最少要挖多少块土
Examples
Input
7 7 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 7 7 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 8 8 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1
Output
2 3 2
Hint
提示：样例解释见下图
Solution C++
#include <stdio.h> #include <string.h> #include <algorithm> #include <queue> using namespace std; struct node{ int x,y,t; }; bool operator < (node i,node j){ return i.t>j.t; } priority_queue<node>q; bool vis[12][12]; int map[12][12]; int n,m,ans; int dx[]={0,1,0,-1}; int dy[]={-1,0,1,0}; inline void bfs(int x,int y){ node vw,vn; while(!q.empty()) q.pop(); vn.x=x,vn.y=y,vn.t=0; if(map[x][y]==1) vn.t++; q.push(vn); memset(vis,0,sizeof(vis)); vis[x][y]=1; while(!q.empty()){ vn=q.top(),q.pop(); if(vn.x==n){ ans=min(ans,vn.t); } if(vn.t>=ans){ return; } for(int i=0;i<4;i++){ int a=vn.x+dx[i]; int b=vn.y+dy[i]; if(a>=1&&a<=n&&b>=1&&b<=m&&!vis[a][b]){ vw.x=a,vw.y=b,vw.t=vn.t; vis[a][b]=1; if(map[a][b]==1) vw.t++; q.push(vw); } } } } int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&map[i][j]); } } ans=10000; for(int i=1;i<=m;i++){ bfs(1,i); } printf("%d\n",ans); } return 0; }
Hint
提示：样例解释见下图