這題在DFS的同時必須考慮剪枝，，給出三個別人的代碼，一個耗時7秒多，一個2秒多，最后一個只有46MS，相差甚大，都是剪枝的功勞。

?

1 #include <stdio.h> 2 #include <string.h> 3 const int MAX =1002; 4 bool flag = false; 5 bool vist[MAX][MAX]; 6 int s,e,map[MAX][MAX]; 7 int dir[5][3]={{1,0},{0,1},{-1,0},{0,-1}}; 8 void DFS(int x,int y,int cnt,int d) 9 { 10 if(cnt>2||vist[x][y]||flag)return; 11 vist[x][y] = true; 12 for(int i = 0;i < 4;i++) 13 { 14 int a,b,t; 15 a = x + dir[i][0]; 16 b = y + dir[i][1]; 17 if(d!=i) t = cnt +1; 18 else t = cnt; 19 if(a==s&&b==e&&t<=2) 20 {flag = true;return ;} //printf("x-%d y-%d a-%d b-%d\n",x,y,a,b); 21 if(!map[a][b]&&!vist[a][b]) 22 DFS(a,b,t,i); 23 } 24 vist[x][y] = false; 25 } 26 int main() 27 { 28 //freopen("Input.txt","r",stdin); 29 //freopen("Output.txt","w",stdout); 30 int n,m,u,v,q; 31 while(scanf("%d%d",&n,&m),(n||m)) 32 { 33 memset(map,-1,sizeof(map)); 34 for(int i = 1;i <= n;i++) 35 for(int j = 1;j <= m;j++) 36 scanf("%d",&map[i][j]); 37 scanf("%d",&q); 38 while(q--) 39 { 40 scanf("%d%d%d%d",&u,&v,&s,&e); 41 flag = false; 42 memset(vist,false,sizeof(vist)); 43 if(map[u][v]!=map[s][e]||map[u][v]==0); 44 else 45 DFS(u,v,-1,-1); 46 if(flag) 47 puts("YES"); 48 else 49 puts("NO"); 50 } 51 } 52 return 0; 53 }

?

//【解題思路】：dfs+剪枝。其實沒什么好說的，有幾個要注意的地方，第一個是判重，第二個是記住最多僅能夠進行兩次轉向。切記，在判斷到達目標的時候，需要判斷其轉向次數是否超過兩次，表示個人在此處wa了兩次。 純暴力版過了之后。有一個剪枝是：在轉向兩次之后，因為不可轉向，所以接下來必須與之前的方式保持一致，這個優化減少了5s左右的時間，原先是7000ms，現在是2000ms。 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <cmath> #include <string> #include <cctype> #include <map> #include <iomanip>using namespace std;#define eps 1e-8 #define pi acos(-1.0) #define pb push_back #define lc(x) (x << 1) #define rc(x) (x << 1 | 1) #define lowbit(x) (x & (-x)) #define ll long longint stx[4]={-1,0,1,0}; int sty[4]={0,1,0,-1}; int a[1100][1100]; int vis[1100][1100]; int n,m,x,y,xx,yy,q,tmp; bool flag;bool solve(int x,int y,int xx,int yy,int cnt,int dir){int tx,ty;if (x==xx && y==yy && cnt<=2) {return true;}if (a[x][y]!=0 && cnt!=-1) return false;if (cnt>2) return false;else {if (cnt==2){ //優化部分vis[x][y]=tmp;tx=x+stx[dir];ty=y+sty[dir];if (tx>=0 && tx<n && ty>=0 && ty<m && vis[tx][ty]!=tmp){if (solve(tx,ty,xx,yy,cnt,dir)) return true;}vis[x][y]=0;} //endelse{vis[x][y]=tmp;for (int i=0; i<4; i++){tx=x+stx[i];ty=y+sty[i];if (tx>=0 && tx<n && ty>=0 && ty<m && vis[tx][ty]!=tmp){if (cnt==-1) {if (solve(tx,ty,xx,yy,cnt+1,i)) return true;}else {if (i!=dir) {if (solve(tx,ty,xx,yy,cnt+1,i)) return true;}else {if (solve(tx,ty,xx,yy,cnt,dir)) return true;}} }}vis[x][y]=0;} }return false; }int main() {while (~scanf("%d%d",&n,&m)){if (n==0 && m==0) break;for (int i=0; i<n; i++){for (int j=0; j<m; j++)scanf("%d",&a[i][j]);}memset(vis,0,sizeof(vis));scanf("%d",&q);for (int i=1; i<=q; i++){scanf("%d%d%d%d",&x,&y,&xx,&yy);x--;y--;xx--;yy--;tmp=i;vis[x][y]=tmp;if (a[xx][yy]!=a[x][y] || (a[x][y]==a[xx][yy] && a[x][y]==0)) {printf("NO\n"); continue;}if (xx==x && yy==y) {printf("NO\n"); continue;}flag=false;if (solve(x,y,xx,yy,-1,-1)==true) { printf("YES\n");}else printf("NO\n");}}return 0; }

?

? /* 本題純屬中文，題意很好理解，主要說下需要注意的幾點。。 1。首先需要判斷給定的倆個棋子是否相同 2。如果給定的坐標沒有棋子直接輸出NO 3。如果給定的坐標是同一個，也直接輸出NO。。不知道測試數據里有沒有這么惡心的數據，不過小心為上吧。。 3。本題搜索需要一點方向感。盲目搜索必定超時，因為本題可以進行倆次轉向。。所以可以分為三種情況。我用turn來標記轉向的次數 turn=0 則直接進行下一步搜索。 turn=1 則需要判斷 狀態的方向 dir 是否與 需要尋找的棋子位置反向了。。如果反向則放棄搜索、、 turn=2 則判斷是否和目標棋子在一條直線上，而且需要判斷方向是否一致。。否則放棄搜索。。 */
/*

46MS

3236K

*/
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; int n,m; int move[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; bool used[1005][1005]; int flag; struct State {int x;int y;int dir;int turn;int step; }; State start; State end; int map[1005][1005]; bool Judge(State t) {if(t.x==end.x&&t.y==end.y)return 1;if(t.turn==0)return 1;if(t.turn==1){if(t.x>end.x&&t.dir==1)return 0;if(t.y>end.y&&t.dir==3)return 0;if(t.x<end.x&&t.dir==0)return 0;if(t.y<end.y&&t.dir==2)return 0;return 1;}if(t.turn==2){if(t.x==end.x){if(t.y>end.y&&t.dir==2)return 1;if(t.y<end.y&&t.dir==3)return 1;}if(t.y==end.y){if(t.x>end.x&&t.dir==0)return 1;if(t.x<end.x&&t.dir==1)return 1;}return 0;}return 1; } void DFS(State t) {if(flag)return;if(t.turn>2)return;if(t.x==end.x&&t.y==end.y){flag=1;return;}int x,y;State temp;if(t.step==0){for(int i=0;i<4;i++){temp.x=t.x+move[i][0];temp.y=t.y+move[i][1];if(temp.x<=0||temp.y<=0||temp.x>n||temp.y>m||used[temp.x][temp.y]==1)continue;temp.dir=i;temp.turn=0;temp.step=t.step+1;if(Judge(temp)==0)continue;used[temp.x][temp.y]=1;DFS(temp);used[temp.x][temp.y]=0;}return;}if(map[t.x][t.y]!=0)return;for(int i=0;i<4;i++){temp.x=t.x+move[i][0];temp.y=t.y+move[i][1];if(temp.x<=0||temp.y<=0||temp.x>n||temp.y>m||used[temp.x][temp.y]==1)continue;if(t.dir!=i){temp.dir=i;temp.turn=t.turn+1;}else{temp.dir=t.dir;temp.turn=t.turn;}temp.step=1;if(Judge(temp)==0)continue;used[temp.x][temp.y]=1;DFS(temp);used[temp.x][temp.y]=0;} } int main() {#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint t;while(scanf("%d %d",&n,&m)){if(n==0&&m==0)return 0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&map[i][j]);scanf("%d",&t);while(t--){scanf("%d %d %d %d",&start.x,&start.y,&end.x,&end.y);if(start.x==end.x&&start.y==end.y){printf("NO\n");continue;}if(map[start.x][start.y]!=map[end.x][end.y]||map[start.x][start.y]==0||map[end.x][end.y]==0){printf("NO\n");continue;}memset(used,0,sizeof(used));used[start.x][start.y]=1;start.turn=0;start.step=0;flag=0;DFS(start);if(flag)printf("YES\n");elseprintf("NO\n");}}return 0; }

?

?

轉載于:https://www.cnblogs.com/Lee-geeker/p/3234419.html

總結

以上是生活随笔為你收集整理的HDOJ 1175 连连看 DFS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。