【競技プログラミング】全てのマス目を一度だけ通る単一の閉曲線

AOJ 0236 Alien Messagesを解いていて詰まってしまったのでアドバイス頂きたいです。

0(通れる),1(通れない)でマップが与えられて、
そのマップに全ての0のマス目を一度だけ通る単一の閉曲線が描けるかどうかを判定する
という問題に対して、DFSで閉曲線がかけるかどうか判定するプログラムを書き、
ナイーブな実装だとTLEなので以下の条件で枝刈りをすることにしました。
(space_sumは0のマスの個数を表します)
・space_sumが4より少なかったらそもそも閉曲線がかけない
・space_sumが偶数でなければそもそも閉曲線がかけない
・DFSで今見ているマス(1にしてある)に隣接するマスおよびスタートのマスに隣接するマス以外で隣接するまだ見ていない(1にされていない)マスの個数が1のマスが存在したら突き当たりになるので閉曲線がかけない。

これで制限時間以内には通りましたが、WAになってしまいました。
そもそも上記の条件が間違っているのでしょうか、それとも実装にミスがあるのでしょうか。
コードを何度も確認してみたのですがどこが間違っているのか私にはわかりませんでした。
お判りの方おられましたら、コメント頂ければ幸いです。
宜しくお願い致します。

lang
1#include <iostream>
2#include <stdio.h>
3#include <sstream>
4#include <string>
5#include <vector>
6#include <map>
7#include <queue>
8#include <algorithm>
9#include <set>
10#include <math.h>
11#include <utility>
12#include <stack>
13#include <string.h>
14#include <complex>
15using namespace std;
16const int INF = 1<<29;
17const double EPS = 1e-8;
18typedef vector<int> vec;
19typedef vector<vec> mat;
20typedef pair<int,int> P;
21struct edge{int to,cost;};
22
23const int dx[] = {0,0,1,-1};
24const int dy[] = {1,-1,0,0};
25
26int field[7][7];
27int space_sum;
28int W, H;
29int sy, sx;
30
31int get_dim(int y, int x){
32    int dim = 0;
33    for(int k=0;k<4;k++){
34        int nx = x + dx[k], ny = y + dy[k];
35        if(nx<0||W<=nx||ny<0||H<=ny)continue;
36        if(field[ny][nx]==0) dim++;
37    }
38    return dim;
39}
40
41bool dfs(int y, int x, int d_sum){
42    if(d_sum==space_sum){
43        if(abs(sy-y)+abs(sx-x)==1)return true;
44    }else{
45        for(int i=0;i<H;i++){
46            for(int j=0;j<W;j++){
47                if(field[i][j]) continue;
48                if(abs(sy-i)+abs(sx-j)==1||abs(y-i)+abs(x-j)==1) continue;
49                if(get_dim(i, j)==1) return false;
50            }
51        }
52        for(int i=0;i<4;i++){
53            int nx = x + dx[i], ny = y + dy[i];
54            if(nx<0||W<=nx||ny<0||H<=ny)continue;
55            if(field[ny][nx]==0){
56                field[ny][nx] = 1;
57                if (dfs(ny, nx, d_sum+1)) return true;
58                field[ny][nx] = 0;
59            }
60        }
61    }
62    return false;
63}
64
65int main(){
66    while(cin >> W >> H, W){
67        space_sum = 0;
68        sy = -1; sx = -1;
69        for(int i=0;i<H;i++){
70            for(int j=0;j<W;j++){
71                scanf("%d",&field[i][j]);
72                space_sum += !field[i][j];
73                if(sy<0&&!field[i][j]){
74                    sy = i; sx = j;
75                }
76            }
77        }
78        field[sy][sx] = 1;
79        if(space_sum<4||space_sum%2==1||!dfs(sy, sx, 1)){
80            cout << "NO" << endl;
81            continue;
82        }else{
83            cout << "YES" << endl;
84        }
85    }
86
87    return 0;
88}
89