oj.uz

Submission #10935

# Submission time Handle Problem Language Result Execution time Memory
10935 2014-11-11T16:20:32 Z dohyun0324 Portals (BOI14_portals) C++
20 / 100
 12 ms 37836 KB 
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
typedef pair<int,int> ppair;
priority_queue<ppair,vector<ppair>,greater<ppair> >arr;
char s[1010],a[1010][1010];
int n,m,p,r=-1,f=-1,ex,ey,sx,sy,dis[1010][1010],ch[1010][1010];
int left[1010][1010],right[1010][1010],down[1010][1010],up[1010][1010];
int xx[5]={0,1,0,-1,0};
int yy[5]={0,0,1,0,-1};
struct data
{
    int x,y,lev;
}q[1000010];
void bfs1()
{
    int i,kx,ky;
    while(f!=r)
    {
        f++;
        for(i=1;i<=4;i++)
        {
            kx=q[f].x+xx[i]; ky=q[f].y+yy[i];
            if(ch[kx][ky] || a[kx][ky]=='#' || a[kx][ky]==0) continue;
            ch[kx][ky]=1;
            r++; q[r].x=kx; q[r].y=ky; q[r].lev=q[f].lev+1; dis[kx][ky]=q[r].lev;
        }
    }
}
void bfs2()
{
    int i,x,y,lev,kx,ky;
    f=-1, r=0;
    memset(ch,0,sizeof ch);
    arr.push(make_pair(0,sx*(m+1)+sy)); ch[sx][sy]=1;
    while(arr.size())
    {
        x=arr.top().second/(m+1); y=arr.top().second%(m+1); lev=arr.top().first;
        arr.pop();
        for(i=1;i<=4;i++)
        {
            kx=x+xx[i]; ky=y+yy[i];
            if(ch[kx][ky] || a[kx][ky]=='#' || a[kx][ky]==0) continue;
            ch[kx][ky]=1;
            arr.push(make_pair(lev+1,kx*(m+1)+ky));
            if(kx==ex && ky==ey){printf("%d",lev+1); return;}
        }
        for(i=1;i<=4;i++)
        {
            if(i==1) kx=left[x][y]/(m+1), ky=left[x][y]%(m+1);
            if(i==2) kx=right[x][y]/(m+1), ky=right[x][y]%(m+1);
            if(i==3) kx=down[x][y]/(m+1), ky=down[x][y]%(m+1);
            if(i==4) kx=up[x][y]/(m+1), ky=up[x][y]%(m+1);
            if(ch[kx][ky] || a[kx][ky]=='#' || a[kx][ky]==0) continue;
            ch[kx][ky]=1;
            arr.push(make_pair(dis[x][y]+lev+1,kx*(m+1)+ky));
            if(kx==ex && ky==ey){printf("%d",dis[x][y]+lev+1); return;}
        }
    }
}
int main()
{
    int i,j;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%s",s);
        for(j=1;j<=m;j++)
        {
            a[i][j]=s[j-1];
            if(a[i][j]=='C') ex=i, ey=j;
            if(a[i][j]=='S') sx=i, sy=j;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(a[i-1][j]=='#' || a[i][j-1]=='#' || a[i+1][j]=='#' || a[i][j+1]=='#' || a[i-1][j]==0 || a[i][j-1]==0 || a[i+1][j]==0 || a[i][j+1]==0)
            {
                r++; q[r].x=i; q[r].y=j; ch[i][j]=1;
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        p=0;
        for(j=1;j<=m;j++)
        {
            if(a[i][j]=='#') p=j;
            else left[i][j]=i*(m+1)+p+1;
        }
        p=m+1;
        for(j=m;j>=1;j--)
        {
            if(a[i][j]=='#') p=j;
            else right[i][j]=i*(m+1)+p-1;
        }
    }
    for(i=1;i<=m;i++)
    {
        p=0;
        for(j=1;j<=n;j++)
        {
            if(a[j][i]=='#') p=j;
            else up[j][i]=(p+1)*(m+1)+i;
        }
        p=n+1;
        for(j=n;j>=1;j--)
        {
            if(a[j][i]=='#') p=j;
            else down[j][i]=(p-1)*(m+1)+i;
        }
    }
    bfs1();
    bfs2();
    return 0;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37836 KB Output is correct
2 Correct 0 ms 37836 KB Output is correct
3 Correct 0 ms 37836 KB Output is correct
4 Correct 0 ms 37836 KB Output is correct
5 Correct 0 ms 37836 KB Output is correct
6 Correct 0 ms 37836 KB Output is correct
7 Incorrect 0 ms 37836 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37836 KB Output is correct
2 Correct 0 ms 37836 KB Output is correct
3 Correct 0 ms 37836 KB Output is correct
4 Correct 0 ms 37836 KB Output is correct
5 Correct 0 ms 37836 KB Output is correct
6 Correct 0 ms 37836 KB Output is correct
7 Incorrect 0 ms 37836 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37836 KB Output is correct
2 Correct 0 ms 37836 KB Output is correct
3 Correct 0 ms 37836 KB Output is correct
4 Correct 0 ms 37836 KB Output is correct
5 Correct 4 ms 37836 KB Output is correct
6 Correct 12 ms 37836 KB Output is correct
7 Correct 4 ms 37836 KB Output is correct
8 Correct 4 ms 37836 KB Output is correct

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37836 KB Output is correct
2 Correct 0 ms 37836 KB Output is correct
3 Correct 0 ms 37836 KB Output is correct
4 Correct 0 ms 37836 KB Output is correct
5 Correct 0 ms 37836 KB Output is correct
6 Correct 0 ms 37836 KB Output is correct
7 Incorrect 0 ms 37836 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37836 KB Output is correct
2 Correct 0 ms 37836 KB Output is correct
3 Correct 0 ms 37836 KB Output is correct
4 Correct 0 ms 37836 KB Output is correct
5 Correct 0 ms 37836 KB Output is correct
6 Correct 0 ms 37836 KB Output is correct
7 Incorrect 0 ms 37836 KB Output isn't correct
8 Halted 0 ms 0 KB -