sicily 1135 飞越原野

//广搜较难 /*题意 m*n矩阵，每个点有可能是湖泊，或者陆地，计算从(0,0)到(m,n)最小步数 超人可以飞，但是不能停在湖泊上，超人的能量能飞D步(从1到3算两步) */ //WA了很多次，一开始处理成只能在湖泊上飞。。傻X得 //做法是典型BFS，虽然状态数高达10000*100(100存超人能量消耗)，实际上广搜可以保证路径递增 //所以可以通过存储已搜的最小能量消耗剪枝 //wengsht #include <iostream> #include <cstdio> #include <queue> #include <cstring> using namespace std; int m,n,d,final; char s[102]; int a[] = {1,-1,0,0}, b[] = {0,0,1,-1}; struct Pair { int v,u; //v = x*n+m u=当前飞行距离 Pair(int v,int u) { this->v = v; this->u = u; } }; struct Node { Node() : mn(101) { } int mn; //表示当前搜到的最小飞行(广搜保证此后不用继续搜飞行路径大于等于mn的此点) bool p; //是否为陆地 int path[101]; //path[i] 此点用i个飞行 最小路径 }node[10111]; //n*m <= 10000个状态 int main() { //freopen("1.txt","r",stdin); scanf("%d%d%d",&m,&n,&d); final = n*m-1; for( int i = 0;i < m;i++ ) { scanf("%s",s); int k = i*n; for( int j = 0;j < n;j++ ) node[k+j].p = ( s[j] == 'P' ? true:false ); } node[final].p = true; if( final == 0 ) { printf("0/n");return 0; } queue<Pair> q; q.push( Pair(0,0) ); node[0].mn = 0; node[0].path[0] = 0; while( !q.empty() ) { int now = q.front().v,d_now = q.front().u; q.pop(); for( int i = 0;i <= 3;i++ ) //转移 { int a_now = now/n,b_now = now%n; int d_nxt = 0; //循环搜同在一方向上所有陆地 for( a_now += a[i],b_now += b[i];a_now >= 0 && a_now < m && b_now >= 0 && b_now < n;a_now += a[i],b_now += b[i] ) { if( d_nxt ) d_nxt++; //0的时候不用飞 if( !node[a_now*n+b_now].p ) { if( !d_nxt ) d_nxt++; continue; } int d_all = d_nxt+d_now; if( !d_nxt ) d_nxt++; int nxt = a_now*n+b_now; //剪枝 if( node[nxt].mn <= d_all || d_all > d ) continue; node[nxt].path[d_all] = node[now].path[d_now] + 1; node[nxt].mn = d_all; //刷新能量上界 if( nxt == final ) { printf("%d/n",node[nxt].path[d_all]); return 0; } q.push( Pair(nxt,d_all) ); } } } printf("impossible/n"); return 0; }