首页 > 代码库 > BZOJ 2346 Lamp
BZOJ 2346 Lamp
不建边表是一定比建边表要快的。
对角线跑最短路。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#define maxn 550#define inf 2000000000using namespace std;int n,m,map[maxn][maxn][5],dis[maxn][maxn];int dx[]={0,-1,-1,1,1},dy[]={0,-1,1,1,-1};queue <int> q;bool vis[maxn][maxn];char s[maxn];bool judge(int x,int y){ if ((x>=1) && (x<=n+1) && (y>=1) && (y<=m+1)) return true; return false;}void spfa(){ for (int i=1;i<=n+1;i++) for (int j=1;j<=m+1;j++) dis[i][j]=inf; dis[1][1]=0;q.push(1);q.push(1);vis[1][1]=true; while (!q.empty()) { int hx,hy; hx=q.front();q.pop();hy=q.front();q.pop(); for (int i=1;i<=4;i++) { int tx=hx+dx[i],ty=hy+dy[i]; if ((judge(tx,ty)) && (dis[tx][ty]>dis[hx][hy]+map[hx][hy][i])) { dis[tx][ty]=dis[hx][hy]+map[hx][hy][i]; if (!vis[tx][ty]) {q.push(tx);q.push(ty);vis[tx][ty]=true;} } } vis[hx][hy]=false; }}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%s",s); for (int j=1;j<=m;j++) { if (s[j-1]==‘/‘) {map[i][j][3]=map[i+1][j+1][1]=1;map[i][j+1][4]=map[i+1][j][2]=0;} else {map[i][j+1][4]=map[i+1][j][2]=1;map[i][j][3]=map[i+1][j+1][1]=0;} } } spfa(); if (dis[n+1][m+1]!=inf) printf("%d\n",dis[n+1][m+1]); else printf("NO SOLUTION\n"); return 0;}
BZOJ 2346 Lamp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。