[uva] 225 - 골리곤스(dfs 구덩이)

ffs의 경로 문제는 구덩이가 같은 노선으로 같은 모퉁이를 갈 수 없기 때문에 처음에 BFS가 저장한 상태가 시간을 초과한 후에 dfs가 지나간 것을 거슬러 올라간다.
난이도가 별로 없는 것 같아요.
이것은 TEL의 BFS 코드입니다.
13970312
225
Golygons
Time limit exceeded
C++
3.000
2014-07-31 09:42:55

#include <vector>
#include <list>
#include <map>
#include <string>
#include <set>
#include <cstring>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXD 1000
#define LEN  300
int n;
int Map[MAXD][MAXD] = {0};
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; /*   ，   ，   ，   */
int dir_[2][2][2] = {{{0,1},{0,-1}},{{1,0},{-1,0}}};
char const _dir[] = "ewns";
/*0 1 2 3       ，  ，  ，  */
struct State{
    vector<int>rote;  /*  */
    int now_dir;      /*    */
    int step;         /*       */
    int x,y;          /*    */
};
bool can_move(int from_x,int from_y,int to_x,int to_y){
    /*     (from_x,from_y)    (to_x,to_y) */
    if(from_x == to_x){
        int t1 = min(from_y,to_y);
        int t2 = max(from_y,to_y);
        for(int i = t1 ; i <= t2 ; i++){
            if(Map[to_x][i])
                return false;
        }
    }
    else if(from_y == to_y){
        int t1 = min(from_x,to_x);
        int t2 = max(from_x,to_x);
        for(int i = t1 ; i <= t2 ; i++){
            if(Map[i][to_y])
                return false;
        }
    }
    return true;
}
void bfs(){
    queue<State>q;
    for(int i = 0 ; i < 4 ; i++){  /*   */
        int _x = LEN + dir[i][0];
        int _y = LEN + dir[i][1];
        if(!Map[_x][_y]){ /*    */
            State start;
            start.rote.push_back(i);
            start.step = 2;
            start.now_dir = i;
            start.x = _x;
            start.y = _y;
            q.push(start);
        }
    }
    int cnt = 0;
    while(!q.empty()){
        State s = q.front(); q.pop();
        if(s.step == n + 1){
            cnt ++;
            for(int i = 0 ; i < s.rote.size(); i++)
                printf("%c",_dir[s.rote[i]]);
            printf("
");
            continue;
        }
        int k;
        int step = s.step;
        if(s.now_dir == 0 || s.now_dir == 1)
            k = 0;
        else
            k = 1;
        for(int i = 0; i < 2 ; i++){ /*     90   */
             int _x = s.x + step * dir_[k][i][0];
             int _y = s.y + step * dir_[k][i][1];
             if(can_move(s.x,s.y,_x,_y)){
                 State temp = s;
                 temp.x = _x; temp.y = _y;
                 temp.step = step + 1;
                 if(k == 0){    /*       */
                    if(i == 0){
                    temp.rote.push_back(2);
                    temp.now_dir = 2;
                    }
                    else
                    if(i == 1) { /*       */
                    temp.rote.push_back(3);
                    temp.now_dir = 3;
                    }
                 }
                 else if(k == 1){
                    if(i == 0){  /*       */
                    temp.rote.push_back(0);
                    temp.now_dir = 0;
                    }
                    else
                    if(i == 1){  /*       */
                    temp.rote.push_back(1);
                    temp.now_dir = 1;
                    }
                 }
                 if(step == n &&(_x != LEN ||_y != LEN)) continue;
                 else
                 q.push(temp);
             }
        }
    }
    printf("Found %d golygon(s).
",cnt);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int m;
        scanf("%d%d",&n,&m);
        memset(Map,0,sizeof(Map));
        for(int i = 0 ; i < m ; i++){
            int x , y;
            scanf("%d%d",&x,&y);
            Map[LEN + x][LEN + y] = 1;
        }
        bfs();
        printf("
");
    }
    return 0;
}

이것은 AC의 DFS 코드로 서로 다른 상황에서 DFS와 BFS를 사용하는 계산 시간의 차이가 매우 크다는 것을 알 수 있다.
13970729
225
Golygons
Accepted
C++
2.239
2014-07-31 10:49:47

#include <vector>
#include <list>
#include <map>
#include <string>
#include <set>
#include <cstring>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXD 1000
#define LEN  500
int n,cnt;
int Map[MAXD][MAXD];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; /*   ，   ，   ，   */
int dir_[2][2][2] = {{{0,1},{0,-1}},{{1,0},{-1,0}}};
char const _dir[] = "ewns";
int _vis[50] = {0};
/*0 1 2 3       ，  ，  ，  */
int rote[MAXD];  /*  */
int vis[MAXD][MAXD];
struct Dir{
    char str[MAXD];
    friend bool operator < (Dir p,Dir q){
        if(strcmp(p.str,q.str) < 0)
            return true;
        else
            return false;
    }
}ans[200L];
void biao(){
    _vis[1] = 1;    _vis[2] = 1;    _vis[3] = 1;    _vis[4] = 1;
    _vis[5] = 1;    _vis[6] = 1;    _vis[9] = 1;    _vis[10] = 1;
    _vis[11] = 1;   _vis[12] = 1;   _vis[13] = 1;   _vis[14] = 1;
    _vis[17] = 1;   _vis[18] = 1;   _vis[19] = 1;   _vis[20] = 1;
}
bool can_move(int from_x,int from_y,int to_x,int to_y){
    /*     (from_x,from_y)    (to_x,to_y) */
    if(from_x == to_x){
        int t1 = min(from_y,to_y);
        int t2 = max(from_y,to_y);
        for(int i = t1 ; i <= t2 ; i++){
            if(Map[to_x][i])
                return false;
        }
    }
    else if(from_y == to_y){
        int t1 = min(from_x,to_x);
        int t2 = max(from_x,to_x);
        for(int i = t1 ; i <= t2 ; i++){
            if(Map[i][to_y])
                return false;
        }
    }
    return true;
}
void dfs(int step,int dir,int x,int y){ /*    ，    ，    */
     vis[x][y] = 1;
     if(step == n && x == LEN && y == LEN){
        for(int i = 0 ; i < step ; i++)
            ans[cnt].str[i] = _dir[rote[i]];
        ans[cnt].str[step] = '\0';
        cnt ++;
        return ;
    }
    else if(step == n)
        return ;
    int k;
    if(dir == 0 || dir == 1)
        k = 0;
    else
        k = 1;
    for(int i = 0; i < 2 ; i++){ /*     90   */
         int _x = x + (step + 1) * dir_[k][i][0];
         int _y = y + (step + 1) * dir_[k][i][1];
         if(!vis[_x][_y] && can_move(x,y,_x,_y)){
             if(k == 0){    /*       */
                if(i == 0){
                rote[step] = 2;
                dfs(step + 1,2,_x,_y);
                }
                else
                if(i == 1) { /*       */
                rote[step] = 3;
                dfs(step + 1,3,_x,_y);
                }
             }
             else if(k == 1){
                if(i == 0){  /*       */
                rote[step] = 0;
                dfs(step + 1,0,_x,_y);
                }
                else
                if(i == 1){  /*       */
                rote[step] = 1;
                dfs(step + 1,1,_x,_y);
                }
             }
             vis[_x][_y] = 0;
         }
     }
     return ;
}
int main(){
    int T;
    scanf("%d",&T);
    biao();
    while(T--){
        int m;
        cnt = 0;
        scanf("%d%d",&n,&m);
        memset(Map,0,sizeof(Map));
        for(int i = 0 ; i < m ; i++){
            int x , y;
            scanf("%d%d",&x,&y);
            Map[LEN + x][LEN + y] = 1;
        }
        if(!_vis[n]){
        for(int i = 0 ; i < 4 ; i++){
            int x = LEN + 1 * dir[i][0];
            int y = LEN + 1 * dir[i][1];
            memset(vis,0,sizeof(vis));
            rote[0] = i;
            dfs(1,i,x,y);
        }
        sort(ans,ans + cnt);
        for(int i = 0 ; i < cnt ; i++)
        printf("%s
",ans[i].str);
        }
        printf("Found %d golygon(s).
",cnt);
        printf("
");
    }
    return 0;
}