公主被恶人抓走, 被关押在牢房的某个地方. 牢房用 N*M (N, M <= 200)的矩阵来表示. 矩阵中的每项可以代表道路(@), 墙壁(#), 和守卫(x).
英勇的骑士 (r) 决定孤身一人去拯救公主(a). 我们假设拯救成功的表示是 "骑士到达了公主所在的位置". 由于在通往公主所在位置的道路中可能遇到守卫, 骑士一旦遇到守卫, 必须杀死守卫才能继续前进.
现假设骑士可以向上, 下, 左, 右四个方向移动, 每移动一个位置需要 1 个单位时间, 杀死一个守卫需要花费额外的 1 个单位时间. 同时假设骑士足够强壮, 有能力杀死所有的守卫.
给定牢房矩阵, 公主, 骑士和守卫在矩阵中的位置, 请你计算拯救行动成功需要花费最短时间.
Input 第一行为一个整数 S, 表示输入的数据的组数(多组输入)
随后有 S 组数据, 每组数据按如下格式输入
1, 两个整数代表 N 和 M, (N, M <= 200).
2, 随后 N 行, 每行有 M 个字符."@" 代表道路,"a" 代表公主,"r" 代表骑士,"x" 代表守卫, "#" 代表墙壁. Output 如果拯救行动成功, 输出一个整数, 表示行动的最短时间.
如果不可能成功, 输出 "Impossible"Sample Input
- 2
- 7 8
- #@#####@
- #@a#@@[email protected]
- #@@#[email protected]@@
- @@#@@#@#
- #@@@##@@
- @#@@@@@@
- @@@@@@@@
- 13 40
- @[email protected]@##[email protected]#[email protected]#xxxx##@#[email protected]@@#x#@#x#@@[email protected]#@x
- xx###[email protected]#@@##[email protected]@@#@[email protected]@#[email protected]@@#[email protected]#[email protected]@[email protected]
- #@x#@x#x#@@##@@x#@xx#[email protected]@x##@@@#@[email protected]@[email protected]
- @##[email protected]@@x#xx#@@#xxxx#@@[email protected]@#@[email protected]@@[email protected]#@#[email protected]#
- @#xxxxx##@@x##[email protected]@@#[email protected]####@@@x#x##@#@
- #xxx#@#x##[email protected]@#[email protected]@@[email protected]#@#[email protected]#####
- #[email protected]#@[email protected]@@@##@x#xx#[email protected]#xx#@#####x#@x
- xx##@#@x##x##x#@x#@a#[email protected]##@#@##[email protected]#@@[email protected]
- x#x#@[email protected]#x#@##@[email protected]#[email protected]##x##xx#@#[email protected]@
- #[email protected]@#@###x##[email protected]#@@#@@[email protected]@@[email protected]@@@##@@[email protected]@x
- x#[email protected]###@xxx#@#x#@@###@#@##@x#@[email protected]#@@#@@
- #@#[email protected]#x#x###@[email protected]@xxx####[email protected]##@x####xx#@x
- #x#@x#x######@@#[email protected]#xxxx#[email protected]@@#xx#x#####@
- Sample Output
- 13 7
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<algorithm>
- #include<queue>
- using namespace std;
- int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
- int a[202][202],b[202][202];
- struct node
- {
- int x,y,t;
- };
- int main()
- {
- int t;
- cin>>t;
- queue<node>q;
- node now,next;
- while(t--)
- {
- memset(a,-1,sizeof(a));
- int xq,yq,n,xz,yz,m;
- cin>>n>>m;
- char c;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- {
- cin>>c;
- if(c=='@')
- a[i][j]=1;
- if(c=='x')
- a[i][j]=2;
- if(c=='r')
- now.x=i,now.y=j;
- if(c=='a')
- xz=i,yz=j;
- b[i][j]=4002149;
- }
- now.t=0;
- long long ans=49021042112;
- q.push(now);
- while(!q.empty())
- {
- now=q.front();
- q.pop();
- for(int i=0;i<4;i++)
- {
- long long xb=now.x+dx[i],yb=now.y+dy[i],bt=now.t;
- if(xb==xz&&yb==yz)
- {
- ans=min(ans,bt);break;
- }
- if(a[xb][yb]!=-1&&bt+a[xb][yb]<b[xb][yb])
- {
- next.t=bt+a[xb][yb];
- next.x=xb,next.y=yb;
- b[xb][yb]=next.t;
- q.push(next);
- }
- }
- }
- if(ans!=49021042112)
- cout<<ans+1<<endl;
- else
- cout<<"Impossible"<<endl;
- }
- }
拯救行动(BFS)
来源: http://www.bubuko.com/infodetail-3184992.html