1、深搜(会爆栈,通过开全局栈模拟递归)
爆栈代码
# include<iostream>
# include<string>
# include<string.h>
# include<queue>
# include<stdio.h>
# include<math.h>
#include <algorithm>
using namespace std;
int d[][];
void dfs(int i,int j)
{
if(d[i][j]==) return;
else
{
d[i][j] = ;
dfs(i-,j);
dfs(i+,j);
dfs(i,j-);
dfs(i,j+);
}
}
int main()
{
int n,m,i,j,w,h;
cin>>n;
while(n--)
{
cin>>w>>h;
d[0][0] = 1;
d[0][h+1] = 1;
d[w+1][0] = 1;
d[w+1][h+1] = 1;
for(i=;i<=w;i++)
{
for(j=;j<=h;j++)
{
if(i==) d[i-][j] = 1;
else if(i==w) d[i+][j] = 1;
else if(j==) d[i][j-] = 1;
else if(j==h) d[i][j+] = 1;
scanf("%d",&d[i][j]);
}
}
int flag = ;
for(i=;i<=w;i++)
{
for(j=;j<=h;j++)
{
if(d[i][j]!= && (i==||i==w||j==||j==h))
{
dfs(i,j);
break;
}
}
if(flag == ) break;
} for(i=;i<=w;i++)
{
for(j=;j<=h;j++)
{
printf("%d ",d[i][j]);
}
printf("\n");
} }
return ;
}
2、广搜(注意w,h输入顺序 先输入h后输入w)
# include<iostream>
# include<string>
# include<string.h>
# include<queue>
# include<stdio.h>
# include<math.h>
#include <algorithm>
using namespace std;
int d[][];
struct Node
{
int x,y;
}node,temp,f[];
queue<Node> q;
void bfs(int x,int y,int w,int h)
{
node.x = x;
node.y = y;
q.push(node);
d[x][y] = ;
while(!q.empty())
{
temp = q.front();
q.pop();
for(int i=;i<;i++)
{
int t1,t2;
t1 = temp.x + f[i].x;
t2 = temp.y + f[i].y;
if(t1>= && t1<=w+ && t2>= && t2<=h+ && d[t1][t2]!=)
{
d[t1][t2] = ;
node.x = t1;
node.y = t2;
q.push(node);
}
}
}
}
int main()
{
int n,m,i,j,w,h;
cin>>n;
f[].x = ;f[].y = ;
f[].x = ;f[].y = -;
f[].x = ;f[].y = ;
f[].x = -;f[].y = ;
while(n--)
{
//cin>>w>>h;
cin>>h>>w;
d[][] = ;
d[][h+] = ;
d[w+][] = ;
d[w+][h+] = ;
for(i=;i<=w;i++)
{
for(j=;j<=h;j++)
{
if(i==) d[i-][j] = ;
else if(i==w) d[i+][j] = ;
if(j==) d[i][j-] = ;
else if(j==h) d[i][j+] = ;
scanf("%d",&d[i][j]);
}
}
bfs(,,w,h);
for(i=;i<=w;i++)
{
for(j=;j<=h;j++)
{
printf("%d ",d[i][j]);
}
printf("\n");
} }
return ;
}