本文主要是介绍HDU-3912 Turn Right 简单搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
主要是题意有点不好理解
题目大意：给你副图 有点个出口 问从这两出口中一进一出（比如出口A,B 可以从A进去B出去走一遍，再从B进去A出来走一遍）
能走的条件为：第一不能有墙，第二，能往右走往右走，不然往前走，再不行就往左走，最后再往后走，问最终能否走遍图中全部格子。
起初不懂怎么存储原图，还是新大神指点迷津
递归DFS会爆栈
#include<stdio.h> #include<iostream> #include<string> #include<string.h> #include<math.h> #include<algorithm> #include<vector> #include<queue> using namespace std; const int maxn = 605; const int inf = 1<<30; int n,m,ans; int xs[] = {0,-1,0,1}; //右上左下 int ys[] = {1,0,-1,0}; int r = 0,u = 1,l = 2,d = 3; struct node {bool wall[4]; }map[maxn][maxn]; bool vis[maxn][maxn]; void DFS( int x,int y,int dir ) {int d;while( 1 ){if( flag || x < 0 || x >= n )break;vis[x][y] = true;for( int i = -1;i <= 2; i ++ ){d = (dir+i+4)%4;if( map[x][y].wall[d] ){x+=xs[d];y+=ys[d];dir = d;break;}}} } void fun() {for( int i = 0; i < n; i ++ )for( int j = 0; j < m; j ++ )if( !vis[i][j] ){puts("NO");return;}puts("YES");} void init() {memset(vis,0,sizeof(vis));for( int i = 0; i <= n; i ++ )for( int j = 0; j <= m; j ++ )for( int k = 0; k < 4; k ++ )map[i][j].wall[k] = 0; } int main() {//freopen("data.txt","r",stdin); int cas,s,e,temp;scanf("%d",&cas);while( cas -- ){scanf("%d%d%d%d",&n,&m,&s,&e);init();for( int i = 0; i < n-1; i ++ ){for( int j = 0; j < m-1; j ++ ){scanf("%d",&temp);if( temp )map[i][j].wall[r] = map[i][j+1].wall[l] = 0;elsemap[i][j].wall[r] = map[i][j+1].wall[l] = 1;}for( int j = 0; j < m; j ++ ){scanf("%d",&temp);if( temp )map[i][j].wall[d] = map[i+1][j].wall[u] = 0;elsemap[i][j].wall[d] = map[i+1][j].wall[u] = 1;}}for( int j = 0; j < m-1; j ++ ){scanf("%d",&temp);if( temp )map[n-1][j].wall[r] = map[n-1][j+1].wall[l] = 0;elsemap[n-1][j].wall[r] = map[n-1][j+1].wall[l] = 1;}map[0][s].wall[u] = 1;map[n-1][e].wall[d] = 1;DFS( 0,s,d );DFS( n-1,e,u);fun();}return 0; }
这篇关于HDU-3912 Turn Right 简单搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
