首页 > 代码库 > 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