BFS+DFS题目_bfs+dfs的题目

BFS 红黑瓷砖

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define check(x,y) (x<Wx && x>=0 && y>=0 && y<Hy)
char room[23][23];
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int Wx,Hy,num;

struct node{int x,y;};

void bfs(int dx,int dy)
{
    num=1;
    queue<node>q;
    node start,next;
    start.x=dx;
    start.y=dy;
    q.push(start);
    while(!q.empty()){
        start=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            next.x=start.x+dir[i][0];
            next.y=start.y+dir[i][1];
            if(check(next.x,next.y) && room[next.x][next.y]=='.'){
                room[next.x][next.y]='#';
                num++;
                q.push(next);
            }
        }
    }

}

int main()
{
   int x,y,dx,dy;
   while(cin>>Wx>>Hy){
      if(Wx==0 &&Hy==0) break;
      for(y=0;y<Hy;y++){
         for(x=0;x<Wx;x++){
             cin>>room[x][y];
             if(room[x][y]=='@') {dx=x,dy=y;}
         }
      }
      num=0;
      bfs(dx,dy);
      cout<<num<<endl;
   }
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

DFS+染色法----油田

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m;
char a[101][101];
int vis[101][101];

void dfs(int x,int y,int color)
{
    int next[8][2]={{0,1},{-1,-1},{-1,1},{1,-1},{1,1},{1,0},{-1,0},{0,-1}};

    a[x][y]=color;
    for(int i=0;i<8;i++)
    {
        int tx=x+next[i][0];
		int ty=y+next[i][1];
		
		if(tx<1 || tx>n || ty<1 || ty>m)
		continue;
		
		if(a[tx][ty]=='@' && vis[tx][ty]==0)
		{
			vis[tx][ty]=1;
			dfs(tx,ty,color);
		}
    }
    return;

}


int main()
{
   while(cin>>n>>m && m)
   {
      for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++)
           cin>>a[i][j];

      memset(vis,0,sizeof(vis));
      int num=0;

      for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++)
             if(a[i][j]=='@')
             {
                 num--;
                 vis[i][j]=1;
                 dfs(i,j,num);
             }
      cout<<-num<<endl;
   }
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

DFS+剪枝----陷落迷宫

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,t,sx,sy,ex,ey,flag,sum=0;
char a[8][8];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},book[8][8];

void dfs(int x,int y,int step)
{
    if(step==t && a[x][y]=='D')
    {
        flag=1;
        return;
    }
    if(flag) return;
    if(step>t) return;
    if((abs(ex-sx)+abs(ey-sy))%2 != t%2) return;
  
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];

        if(tx<1 || tx>n || ty<1 || ty>m) 
          continue;
        
        if(a[tx][ty]!='X' && !book[tx][ty])
        {
            book[tx][ty]=1;
            dfs(tx,ty,step+1);
            book[tx][ty]=0;
        }
    }
}

int main()
{
   while(cin>>n>>m>>t && n||m||t){

   memset(book,0,sizeof(book));
   sum=0;
   flag=0;

   for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
      {
          cin>>a[i][j];
          if(a[i][j]=='S'){
              sx=i;sy=j;
          }
          else if(a[i][j]=='D'){
              ex=i;ey=j;
          }
          else if(a[i][j]=='X')
            sum++;
      }

      if(n*m-sum<=t) {
          cout<<"NO"<<endl;
          continue;
      }
    
    book[sx][sy]=1;
    dfs(sx,sy,0); 

    if(flag) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
   }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

DFS+路径输出----走迷宫

#include <iostream>
#include <algorithm>
using namespace std;
int n,m,sx,sy,ex,ey,flag; //flag用来表示是否存在路径
int a[15][15]; //地图，因为本身就是1或0，所以可以利用而省去标记数组
int ans[50000][2]; //存储解
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};  //方向一定是左下右上

void print(int n) //打印解
{
    flag=1; //有解
    for(int i=1;i<=n;i++)
    {
        if(i<n) printf("(%d,%d)->",ans[i][0],ans[i][1]);
        else printf("(%d,%d)\n",ans[i][0],ans[i][1]);
    }
}

void dfs(int an,int x,int y) //an表示ans[][]的一维下标
{

    for(int i=0;i<4;i++) //直接尝试
    {
        a[x][y]=0; //标记a(x,y)已经走过并不再可走，避免重复走，可以这么做的原因是dfs的x,y参数初始必然可走，即为1

        x=x+dx[i]; //尝试下一点
        y=y+dy[i];

        if(a[x][y])
        {
           ans[an][0]=x;
           ans[an][1]=y;
           if(x==ex && y==ey)
             print(an);
           else 
             dfs(an+1,x,y);
        }

        x-=dx[i];
        y-=dy[i];
        a[x][y]=1; //回溯
    }
}

int main()
{
   cin>>n>>m;
   for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
         cin>>a[i][j];

   cin>>sx>>sy>>ex>>ey;
   ans[1][0]=sx,ans[1][1]=sy;
   dfs(2,sx,sy);
   if(!flag) printf("-1");

   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

BFS----逃离迷宫

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int n,m,t,xx,yy,ans=0,book[505][505][2];
char a[505][505];

struct node
{
	int x,y,f;
};

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1}; 

int bfs(int x,int y)
{
	memset(book,-1,sizeof(book));
	
	queue <node>q;
	book[x][y][0]=0;
	q.push((node){xx,yy,0});
	
	while(!q.empty())
	{
	   node h;
	   h=q.front();
	   q.pop();
	   
	   if(h.f && a[h.x][h.y]=='E')
	   {
	   	 return ans=book[h.x][h.y][1];
	   }
	   
	   for(int i=0;i<4;i++)
	   {
	   	int tx=h.x+dx[i];
	   	int ty=h.y+dy[i];
	   	
	   	if(tx>=1 && tx<=n && ty>=1 && ty<=m && a[tx][ty]!='#')
	   	{
	   		node temp;
	   		if(a[tx][ty]=='K') temp.f=1;//取得钥匙; 
	   		else temp.f=h.f; //先前已有钥匙temp.f也会为1，没有为0 
            if(book[tx][ty][temp.f]!=-1) continue; //已走过，continue;
            if(a[tx][ty]=='E' && h.f==0) continue; //遇到E但是没有钥匙，continue; 
	   
	   		temp.x=tx;
		    temp.y=ty;
	   		book[tx][ty][temp.f]=book[h.x][h.y][h.f]+1; //步数累加 
	   		q.push(temp);
	    }
	    
	   }
	}
	return -1;
}

int main()
{
  cin>>t;
  while(t--){
  	cin>>n>>m;
  	ans=0;
  	memset(a,0,sizeof(a));
  	for(int i=1;i<=n;i++)
  	{
  		for(int j=1;j<=m;j++)
  	   {
  	   	  scanf(" %c",&a[i][j]);
  	   	  if(a[i][j]=='P') {xx=i,yy=j;}
       }
    }
    ans=bfs(xx,yy);
    if(ans>0) cout<<ans<<endl;
    else cout<<"No solution"<<endl;
 
  }
  return 0;
}


/*#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int N,M;
char map[503][503];
int vis[502][502][2];
int d[4][2]={0,1,0,-1,1,0,-1,0};
struct Node{
    int x,y;
    int f;
};
int bfs(int x,int y)
{
    memset(vis,-1,sizeof(vis));
    queue<Node> q;
    Node p;
    p.x=x,p.y=y,p.f=0;
    vis[x][y][p.f]=0;
    q.push(p);
    while(!q.empty())
    {
        p=q.front();q.pop();
        if(map[p.x][p.y]=='E'&&p.f) return vis[p.x][p.y][1];
        for(int i=0;i<4;i++)
        {
            int tx=p.x+d[i][0],ty=p.y+d[i][1];
            if(tx>=0&&tx<N&&ty>=0&&ty<M&&map[tx][ty]!='#')
            {
                Node temp;
                if(map[tx][ty]=='K') temp.f=1;
                else temp.f=p.f;
                if(vis[tx][ty][temp.f]!=-1) continue;
                if(map[tx][ty]=='E'&&temp.f==0) continue;
                temp.x=tx,temp.y=ty;
                vis[tx][ty][temp.f]=vis[p.x][p.y][p.f]+1;
                q.push(temp);
            }
        }
    }
    return -1;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&N,&M);
        for(int i=0;i<N;i++) scanf("%s",map[i]);
        int ans;
        for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
        if(map[i][j]=='P')
        {
            ans=bfs(i,j);break;
        }
        if(ans>0) printf("%d\n",ans);
        else printf("No solution\n");
    }
    
    return 0;
}
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

DFS----单词接龙

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s[21];
int vis[21],maxl=0,n;

bool judge(string s1,string s2,int j) //判断是否有长度为j的相同部分
{
   int e=s1.length();
   string s3(s1,e-j);
   string s4(s2,0,j);
   if(s3==s4) return true;
   return false;
}

string link(string s1,string s2,int j)
{
    int l1=s1.length();
    string s3(s1,0,l1-j);
    string s4=s3+s2;
    return s4;
}

void dfs(string ss)
{
    int sl=ss.length();
   maxl=max(maxl,sl);
   for(int i=0;i<n;i++)
      for(int j=1;j<=ss.length();j++){
          if(vis[i]>=2) continue;
          if(j>s[i].length()) continue;
          if(judge(ss,s[i],j)){
              vis[i]++;
              string temp=link(ss,s[i],j);
              dfs(temp);
              vis[i]--;
          }
      } 
}

int main()
{
   cin>>n;
   for(int i=0;i<n;i++) cin>>s[i];
   string b;
   cin>>b;
   dfs(b);
   cout<<maxl<<endl;

   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

DFS+染色法

#include <stdio.h> 
int a[101][101];
int book[110][110],n,m,sum;

void dfs(int x,int y,int color)
{
	int next[4][2]={{0,1},//right
	                {1,0},//down
	                {-1,0},//up
	                {0,-1}//left
	                };
	
	int k,tx,ty;
	a[x][y]=color;
	
	for(k=0;k<=3;k++) 
	{
		tx=x+next[k][0];
		ty=y+next[k][1];
		
		if(tx<1 || tx>n || ty<1 || ty>m)
		continue;
		
		if(a[tx][ty]>0 && book[tx][ty]==0)
		{
			sum++;
			book[tx][ty]=1;
			dfs(tx,ty,color);
		}
    }             
	return; 
}

int main() 
{
	int i,j,num=0;
	scanf("%d %d\n",&n,&m);
	
	for(i=1;i<=n;i++)
	{ 
	    for(j=1;j<=m;j++)
	      scanf("%1d",&a[i][j]);
	}
	
//对大于0的点进行染色	      
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(a[i][j]>0)
			{
				num--;
				book[i][j]=1;
				dfs(i,j,num);
			}
		}
	}
	
	printf("%d",-num);
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

DFS----图腾

 #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
char s[1025][1025];

void dfs(int k,int x,int y)
{
	if(k==1)
	{
		s[x][y]='/';
		s[x][y+1]='_';
		s[x][y+2]='_';
		s[x][y+3]='\\';
		s[x-1][y+1]='/';
		s[x-1][y+2]='\\';
		return ;
    }
    
    dfs(k-1,x,y);
    dfs(k-1,x,y+(1<<k));
    dfs(k-1,x-(1<<k-1),y+(1<<k-1));
}
 
int main()
{
  int n;
  cin>>n;
  memset(s,(' '),sizeof(s));
  dfs(n,1<<n,1);
  for(int i=1;i<=(1<<n);i++)
  {
  	for(int j=1;j<=(1<<n+1);j++)
  	cout<<s[i][j];
  	
  	if(i!=(1<<n))
  	cout<<endl;
  }
  return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

数的全排列

#include <iostream>
typedef long long ll;
using namespace std;
int n,a[8],book[8]={0};

void dfs(int x)
{
	if(x==n+1) {
			for(int i=1;i<=n;i++)
			printf("    %d",a[i]);
			printf("\n");
			return;
		}
		
	for(int i=1;i<=n;i++)	
	{
		if(book[i]==0)
		{
			a[x]=i;
			book[i]=1;
			dfs(x+1);
			book[i]=0;
		}
	}	
	return; 
}

int main()
{
  cin>>n;
  
  dfs(1);
  return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36