글 읽기 - 신이시여 제가 어디서 실수를 하고 있사옵니까....

s7d8f9 5년 전 0

제바르....30번 넘게 시도중...... 인성을 버릴것 같사옵니다...

4 5

.....

....H

K....

.....

5 5

.....

...H.

.K...

.....

4 5

.....

.K#..

...H.

.....

4 5

.....

.K#..

.#H..

.....

4 5

.....

.K#..

.#H..

#....

4 5

...#.

.K#..

.#H..

#....

4 5

.....

.K...

...H.

.....

4 5

K....

...##

##...

....H

4 5

K....

...##

###..

....H

2 2

다음 예시들은 전부 클리어합니다...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#include <bitset>
#define MAX 125
#define INF 987654321
#define MOD 1000000
//#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int n,m,st[2],fi[2],ans=0,a,b;
int map[MAX][MAX],pre[MAX*MAX*2];
bitset<MAX*MAX*2> flow[MAX*MAX*2];
int dy[2][3]={{0,-1,0},{0,0,1}},dx[2][3]={{0,0,-1},{0,1,0}};
char ch;
queue<int> q;

int tonode(int y,int x){return (y-1)*100+(x-1);};
pi tomap(int val)
{
    val=10000<=val?val-10000:val;
    return make_pair(val/100+1, val%100+1);
};
// 1,1 -> 0으로 저장 2,2 -> 101로 저장 이런방식 사용

int main()
{
    fill_n(&map[0][0],MAX*MAX,2);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        getchar();
        for(int k=1;k<=m;k++)
        {
            scanf("%c",&ch);
            if(ch=='.')
                map[i][k]=1;
            else if(ch=='H')
            {
                map[i][k]=3;
                fi[0]=tonode(i,k);
                fi[1]=fi[0]+10000;
            }
            else if(ch=='K')
            {
                map[i][k]=3;
                st[0]=tonode(i,k);
                st[1]=st[0]+10000;
            }
        }
    }
    // 입력을 받는다.
    for(int i=0;i<2;i++)
        for(int k=1;k<=2;k++)
        if(map[tomap(st[0]).first+dy[i][k]][tomap(st[0]).second+dx[i][k]]==3)
        {
            printf("-1");
            return 0;
        }
    // K와 H가 붙어있는 경우 -1을 출력한다.
    while(1)
    {
        fill_n(&pre[0],MAX*MAX*2,-1);
        q.push(st[0]),q.push(st[1]);
        while(!q.empty())
        {
            int tmp=q.front();
            q.pop();
            pi p=tomap(tmp);
            if(tmp<10000)
            {
                for(int i=0;i<3;i++)
                {
                    a=p.first+dy[0][i],b=p.second+dx[0][i];
                    int next=tonode(a,b)+10000;
                    int f=flow[tmp].test(next)?1:0;
                    if(map[a][b]!=2&&pre[next]==-1&&1-f>0)
                    {
                        pre[next]=tmp;
                        q.push(next);
                        if(next==fi[0]||next==fi[1])
                        {
                            while(!q.empty()){q.pop();};
                            break;
                        }
                    }
                }
            }
            // 한 칸을 두 노드로 했을때 위쪽 노드의 경우
            else
            {
                for(int i=0;i<3;i++)
                {
                    a=p.first+dy[1][i],b=p.second+dx[1][i];
                    int next=tonode(a,b);
                    int f=flow[tmp].test(next)?1:0;
                    if(map[a][b]!=2&&pre[next]==-1&&1-f>0)
                    {
                        pre[next]=tmp;
                        q.push(next);
                        if(next==fi[0]||next==fi[1])
                        {
                            while(!q.empty()){q.pop();};
                            break;
                        }
                    }
                }
            }
            // 한 칸을 두 노드로 했을때 아래쪽 노드의 경우
        }
        if(pre[fi[0]]==-1&&pre[fi[1]]==-1)
            break;
        // 도착지의 두 노드에 도착할 방법이 없을 경우
        else
            ans++;
        // 도착 할 방법이 없다면 플로우 증가
        int cur=pre[fi[0]]==-1?fi[1]:fi[0];
        // 플로우를 늘려준다.(도착지의 두 노드중 도착지에 대해서)
        
        while(cur!=st[0]&&cur!=st[1])
        // 출발지에 도달하면 종료시킨다.
        {
            flow[pre[cur]].set(cur);
            flow[cur].reset(pre[cur]);
            cur=pre[cur];
        }
    }
    printf("%d",ans);
    // 전체 플로우를 출력한다.
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

신이시여 제가 어디서 실수를 하고 있사옵니까....

s7d8f9 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말