제출 #262466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
262466		daniel920712	무지개나라 (APIO17_rainbow)	C++14	11 / 100	3069 ms	1016 KiB

rainbow

#include "rainbow.h"
#include <queue>
#include <utility>
using namespace std;
bool all[55][200005]={0};
bool have[55][200005]={0};
int dx[5]={1,0,-1,0};
int dy[5]={0,-1,0,1};
queue < pair < int , int > > BFS;
void init(int R, int C, int sr, int sc, int M, char *S)
{
    all[sr][sc]=1;
    int i;
    for(i=0;i<M;i++)
    {
        if(S[i]=='N') sr--;
        if(S[i]=='S') sr++;
        if(S[i]=='E') sc++;
        if(S[i]=='W') sc--;
        all[sr][sc]=1;
    }

}

int colour(int ar, int ac, int br, int bc)
{
    int ans=0,x,y,i,j,k;
    for(i=ar;i<=br;i++) for(j=ac;j<=bc;j++) have[i][j]=0;

    for(i=ar;i<=br;i++)
    {
        for(j=ac;j<=bc;j++)
        {
            if(!have[i][j]&&all[i][j]==0)
            {
                ans++;
                BFS.push(make_pair(i,j));
                have[i][j]=1;
                while(!BFS.empty())
                {
                    x=BFS.front().first;
                    y=BFS.front().second;
                    BFS.pop();

                    for(k=0;k<4;k++)
                    {
                        if(x+dx[k]>=ar&&x+dx[k]<=br&&y+dy[k]>=ac&&y+dy[k]<=bc&&!have[x+dx[k]][y+dy[k]]&&!all[x+dx[k]][y+dy[k]])
                        {
                            have[x+dx[k]][y+dy[k]]=1;
                            BFS.push(make_pair(x+dx[k],y+dy[k]));
                        }
                    }
                }
            }


        }
    }
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26