C-迷宫（牛客月赛99

本文主要是介绍C-迷宫（牛客月赛99，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：在n×m的迷宫里，有空地和障碍，有一个超能力：当前位置朝任意方向上所有的障碍物都会清除，超能力最多使用一次，如果可以到终点输出yes

分析：先从终点开始走，将沿路的障碍的横坐标和纵坐标都做上标记，再从起点开始走，如果下一个网格为障碍，判断该方向的坐标是否被做上标记，如果被标记，则可以在该方向上释放超能力。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int n,m,sx,sy,zx,zy;
char a[N][N];
ll ans=0;
int temp[N][N],xx[N],yy[N];
ll dx[4]={0,0,1,-1};
ll dy[4]={-1,1,0,0};
void d(int x,int y){if(x==sx&&y==sy){ans++;return;}for(int i=0;i<4;i++){if(a[x+dx[i]][y+dy[i]]=='#'){xx[x+dx[i]]=1;yy[y+dy[i]]=1;}if(temp[x+dx[i]][y+dy[i]]==0&&(a[x+dx[i]][y+dy[i]]=='E'||a[x+dx[i]][y+dy[i]]=='.'||a[x+dx[i]][y+dy[i]]=='S')){temp[x][y]=1;d(x+dx[i],y+dy[i]);}}
}
void dd(int x,int y){if(x==zx&&y==zy){ans++;return;}for(int i=0;i<4;i++){if(temp[x+dx[i]][y+dy[i]]==0&&(a[x+dx[i]][y+dy[i]]=='E'||a[x+dx[i]][y+dy[i]]=='.'||a[x+dx[i]][y+dy[i]]=='S')){temp[x][y]=1;dd(x+dx[i],y+dy[i]);}else if(temp[x+dx[i]][y+dy[i]]==0&&a[x+dx[i]][y+dy[i]]=='#'){if(yy[y]==1&&dy[i]==0){ans++;return;}else if(xx[x]==1&&dx[i]==0){ans++;return;}}}
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]=='S'){sx=i,sy=j;}else if(a[i][j]=='E'){zx=i,zy=j;}}}d(zx,zy);if(ans>0){cout<<"YES"<<endl;return 0;}dd(sx,sy);if(ans>0)cout<<"YES"<<endl;else cout<<"NO"<<endl;return 0;
}

这篇关于C-迷宫（牛客月赛99的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---