用 bfs 找出最短路, 同时更新到该点的路径条数 ans 用 ans[i][j][f] 表示 i,j 点 f 方向
f 用 0,1,2,3 表示 4 个方向 同时和 dx,dy 数组联系起来
用两个小函数实现转弯和直行两种情况, 直行要 while 一下, 把走的每个长度都算作一步
- #include<bits/stdc++.h>
- using namespace std;
- #define MOD 1000000
- char mp[105][105];
- int ans[105][105][6],visit[105][105][6],step[105][105][6];
- int dx[]={-1,0,1,0};
- int dy[]={0,1,0,-1};
- struct node{
- int x,y,f,st;
- }s,e,q,p;
- int flag,n,m;
- int check()// 转弯
- {
- if(visit[q.x][q.y][q.f]==1){
- if(step[q.x][q.y][q.f]==p.st+1)ans[q.x][q.y][q.f]=(ans[p.x][p.y][p.f]+ans[q.x][q.y][q.f])%MOD;
- return 0;
- }
- else{
- visit[q.x][q.y][q.f]=1;
- ans[q.x][q.y][q.f]=ans[p.x][p.y][p.f];
- q.st=p.st+1;
- step[q.x][q.y][q.f]=q.st;
- return 1;
- }
- }
- int check2()// 直行
- {
- if(q.x<0||q.x>=n||q.y<0||q.y>=m||mp[q.x][q.y]=='*')return 0;
- if(visit[q.x][q.y][q.f]==1){
- if(step[q.x][q.y][q.f]==p.st+1)ans[q.x][q.y][q.f]=(ans[p.x][p.y][p.f]+ans[q.x][q.y][q.f])%MOD;
- return 1;
- }
- else{
- visit[q.x][q.y][q.f]=1;
- ans[q.x][q.y][q.f]=ans[p.x][p.y][p.f];
- q.st=p.st+1;
- step[q.x][q.y][q.f]=q.st;
- return 2;
- }
- }
- void bfs()
- {
- int i;
- if(e.x==s.x&&e.y==s.y){
- printf("0 1\n");
- return;
- }
- memset(visit,0,sizeof visit);
- memset(ans,0,sizeof ans);
- memset(step,0x3f3f3f3f,sizeof step);
- flag=0;
- queue<node>qu;
- qu.push(s);
- ans[s.x][s.y][s.f]=1;
- visit[s.x][s.y][s.f]=1;
- while(!qu.empty()){
- p=qu.front();qu.pop();
- // cout<<"ppp"<<p.x<<p.y<<""<<p.f<<' '<<p.st<<"ans"<<ans[p.x][p.y][p.f]<<endl;
- if(p.x==e.x&&p.y==e.y){
- flag=1;
- step[p.x][p.y][p.f]=p.st;
- continue;
- }
- node n1=p;
- while(1){
- q.x=n1.x+dx[p.f];q.y=n1.y+dy[p.f];q.f=p.f;
- n1.x=q.x,n1.y=q.y;
- int ii=check2();
- if(ii==0)break;
- // cout<<q.x<<"x-y"<<q.y<<" "<<q.st<<endl;
- else if(ii==2)qu.push(q);
- }
- q.x=p.x;q.y=p.y;q.f=(p.f+1)%4;
- if(check())qu.push(q);
- q.x=p.x;q.y=p.y;q.f=(p.f+3)%4;
- if(check())qu.push(q);
- }
- if(flag==0){
- printf("0 0\n");
- return;
- }
- int minn=0x3f3f3f3f,sum=0;
- for(i=0;i<4;i++)minn=min(minn,step[e.x][e.y][i]);
- for(i=0;i<4;i++){
- if(step[e.x][e.y][i]==minn)sum=(sum+ans[e.x][e.y][i])%MOD;
- }
- printf("%d %d\n",minn,sum);
- }
- int main()
- {
- int i,j;
- while(scanf("%d%d",&n,&m),n!=0||m!=0){
- getchar();
- for(i=0;i<n;i++){
- for(j=0;j<m;j++){
- scanf("%c",&mp[i][j]);
- if(mp[i][j]=='X')e.x=i,e.y=j;
- else if(mp[i][j]>='A'&&mp[i][j]<='Z'){
- s.x=i,s.y=j;
- s.st=0;
- if(mp[i][j]=='N')s.f=0;
- else if(mp[i][j]=='S')s.f=2;
- else if(mp[i][j]=='W')s.f=3;
- else s.f=1;
- }
- }
- getchar();
- }
- bfs();
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3530091.html