ZOJ 1708 | | hdu 1035 Robot Motion (체인 전방 향 성, dfs)

이 문 제 는 체인 식 전방 향 성 으로 풀 기 에는 너무 간단 하 다.
             진짜 거의 완벽 한 작품 이 네요.
제목:
    그림 을 따라 가면 N 은 위로, S 는 아래로, E 는 오른쪽으로, W 는 왼쪽으로 간다.
    나 가면 출력 걸음 수.
    링 이 되면 출력 이 몇 걸음 까지 갔 을 때 링 에 부 딪 힌 다음 출력 링 을 한 바퀴 돌 면 얼마나 걸 립 니까?
 
   문제 풀이 방향:  체인 전방 향 성, 아래 dfs 직접 해법 도 있 습 니 다:
  체인 전방 향 성 은 일종 의 데이터 구조 이다.ssfz 신소 Malash 가 창조 한 것 으로 지금까지 널리 알려 진 체인 전방 향 성 이다.완벽 하 다 고 할 수 있다.
  하나의 배열 로 변 의 종점 을 저장 하고, 하나의 배열 로 각 변 의 번 호 를 저장 합 니 다.  한 배열 로 시작 점 의 마지막 출구 번 호 를 저장 합 니 다. 이 번 호 는 저장 변 의 번호 의 배열 에서 이 시작 점 의 모든 출구 번 호 를 색인 하 는 데 사 용 됩 니 다.
  이 점 을 이해 하면 처리 하기 쉽다.
  우 리 는 제목 의 한 걸음 한 걸음 을 한 변 으로 본다.체인 식 앞 에 별 을 향 해 저장 하기 때문에 이 쪽 에 자신 만 의 사 이 드 번호 가 생 겼 다.
  이 변 번 호 는 이 문제 에서 몇 번 째 걸음 으로 볼 수 있다.
  그런 후에 우 리 는 한 걸음 한 걸음 걸 을 때마다 이 점 이 대표 하 는 변 이 체인 식 앞 에 별 을 향 해 존재 한 적 이 있 는 지 판단 한다.저 장 했 으 면 순환 에서 벗 어 나.저 장 된 변 의 번 호 를 직접 출력 합 니 다.순환 할 걸음 수 는 총 변 에서 이 번 호 를 빼 는 것 + 1,
 저금 도 안 해 봤 으 면총 몇 개의 변 이 있 는 지 직접 출력 하면 됩 니 다.
 
  사실 체인 전방 향 성의 용도 가 매우 크다.많은 문제 에 적합 하 다.적은 문 제 는 2 차원 배열 로 풀 면 된다.
  체인 식 전방 향 성의 속도 가 매우 빠르다.추천 
   말 라 시 신 우 를 경 배 하 다.   orz.......
 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1000
typedef struct
{
    int to,next,cap;
} E;
E edge[N*N];
int V[N];
int p[N];
int M;

void insert(int from,int to)
{
    edge[M].to=to;
    edge[M].cap=1;
    edge[M].next=V[from];
    V[from]=M++;
}
int main()
{
    int n,m,s,i,j;
    char str[N][N],c;
    while(scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)break;
        scanf("%d
",&s);
        M=1;
        memset(V,-1,sizeof(V));
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=m ; j++)
            {
                scanf("%c",&str[i][j]);
            }
            getchar();
        }
        i=1;
        while(1)
        {
            c=str[i][s];
            if(V[i]==-1)
            {
            insert(i,s);
            }

            else
            {
                for(j=V[i]; j+1; j=edge[j].next)
                if(edge[j].to==s)
                {
                    break;
                }
                if(!(j+1))
                insert(i,s);
                else break;
            }
            switch(c)
            {
            case 'N':
                i-=1;
                break;
            case 'W':
                s-=1;
                break;
            case 'E':
                s+=1;
                break;
            case 'S':
                i+=1;
                break;
            }
            if(s>m||i>n||!i||!s)break;
        }
        if(!i||!s||i>n||s>m)
        printf("%d step(s) to exit
",M-1);
        else
        {
            printf("%d step(s) before a loop of %d step(s)
",j-1,M-j);
        }
    }

    return 0;
}

  
dfs: 각 점 에 표 시 를 하면 됩 니 다. 표 시 된 것 을 만나면 현재 dfs 층수 에서 이 표 시 를 빼 면 순환 하 는 걸음 수 입 니 다. 그리고 이 표 시 는 순환 돈 이 가 는 걸음 수 입 니 다.
이 코드 는 Zoj 의 것 입 니 다. n | m | k 의 | k 를 삭제 하고 hdu 에 제출 하면 됩 니 다.
코드:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define REP(a,b,c) for(int a = b; a < c; ++a)
#define eps 10e-8

const int MAX_ = 1010;
const int N = 100010;
const int INF = 0x7fffffff;

int C[MAX_];
char str[MAX_][MAX_];
int a[MAX_];
int vis[MAX_][MAX_];

int n, m, k, step, loop;

int dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};

int selectf(char c)
{
    switch(c){
        case 'W':return 1;
        case 'S':return 2;
        case 'E': return 3;
        case 'N': return 0;
    }
}

void dfs(int x, int y, int f)
{
    if(vis[x][y] != -1){
        loop = f-vis[x][y] ;
        step = vis[x][y];
        return ;
    }

    int tmp = selectf(str[x][y]);
    int xx, yy;
    xx = x + dir[tmp][1];
    yy = y + dir[tmp][0];
    vis[x][y] = f;
    if(xx < 0 || xx >= n || yy < 0 || yy >= m){
        step = f+1;
        return ;
    }

    dfs(xx, yy, f+1);

}

int main()
{
    int T;

    while(~scanf("%d%d%d", &n, &m, &k), n||m||k){
        REP(i, 0, n){
            scanf("%s",str[i]);
        }
        mst(vis,-1);
        loop= -1;
        step = -1;
        dfs(0, k-1, 0);
        if(loop == -1){
            printf("%d step(s) to exit
", step);
        }
        else {
            printf("%d step(s) before a loop of %d step(s)
", step, loop);
        }

    }
	return 0;
}