제출 #902789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
902789		vjudge1	무지개나라 (APIO17_rainbow)	C++11	11 / 100	3086 ms	1048576 KiB

rainbow

#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
vector< vector<bool> >matriz;
void init(int R, int C, int sr, int sc, int M, char *S) {
    matriz = vector< vector<bool> > (R,vector<bool>(C,true));
    sr--;
    sc--;
    matriz[sr][sc]=0;
    for(int i=0;i<M;i++){///marcando el camino de la serpiente
        int dir=S[i];
        if(dir=='N')sr--;
        if(dir=='W')sc--;
        if(dir=='S')sr++;
        if(dir=='E')sc++;
        matriz[sr][sc]=0;
    }
}
int colour(int ar, int ac, int br, int bc) {
    ar--;
    ac--;
    br--;
    bc--;
    vector< vector<bool> >visitados(matriz.size(),vector<bool> (matriz[0].size(),false));
    int cont=0;
    for(int i=ar;i<=br;i++){
        for(int j=ac;j<=bc;j++){
            if(matriz[i][j] && !visitados[i][j]){///si no esta pintado y podemos ir por ahí
                visitados[i][j]=1;///lo pintamos
                cont++;///nuevo color
                queue< pair<int,int> >q;///cola donde almacenaremos los caminos
                q.push(make_pair(i,j));///comenzaremos nuestro camino
                while(!q.empty()){
                    int px=q.front().first,py=q.front().second,px1=px-1,py1=py,px2=px,py2=py-1,px3=px+1,py3=py,px4=px,py4=py+1;///designando nuevas direcciones a N,W,S,E
                    q.pop();
                    if(px1>=ar && px1<=br && py1>=ac && py1<=bc){///si es territorio dentro de la zona
                        if(matriz[px1][py1] && !visitados[px1][py1]){///si no esta pintado y podemos ir por ahí
                            visitados[px1][py1]=1;///lo pintamos
                            q.push(make_pair(px1,py1));///nuevo camino
                        }
                    }
                    if(px2>=ar && px2<=br && py2>=ac && py2<=bc){
                          if(matriz[px2][py2] && !visitados[px2][py2]){
                            visitados[px2][py2]=1;
                            q.push(make_pair(px2,py2));
                        }
                    }
                    if(px3>=ar && px3<=br && py3>=ac && py3<=bc){
                       if(matriz[px3][py3] && !visitados[px3][py3]){
                            visitados[px3][py3]=1;
                            q.push(make_pair(px3,py3));
                        }
                    }
                    if(px4>=ar && px4<=br && py4>=ac && py4<=bc){
                         if(matriz[px4][py4] && !visitados[px4][py4]){
                            visitados[px4][py4]=1;
                            q.push(make_pair(px4,py4));
                        }
                    }
                }
            }
        }
    }
    return cont;
}
/*int main(){
    int R,C,M,Q,sr,sc,ar,ac,br,bc;
    string S;
    cin>>R>>C>>M>>Q;
    cin>>sr>>sc;
    cin>>S;
    init(R,C,sr,sc,M,S);
    for(int i=0;i<Q;i++){
        cin>>ar>>ac>>br>>bc;
        int ans=colour(ar,ac,br,bc);
        cout<<ans<<"\n";
    }
    return 0;
}*/

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