poj1548Robots dfs做法

//搜索每一行
//將該行的所有點都清除
//然後再一改行的最後一個點的位置向下走一步
//然後將下面一行的所有點清除
//然後再重復上述操作
#include
#include
#include
using namespace std;
const int maxn=30;
int line[maxn][maxn];
int C,R;
int ans = 0;
void dfs(int x , int y)
{
int pos = y;
for(int j = y ;j <= C ;j++)
if(line[x][j])
{
line[x][j] = 0;
pos = j;
}
if(x == R)return ;
dfs(x+1 , pos);
}
int main()
{
int a,b;
//freopen("in.txt","r",stdin);
while(scanf("%d%d", &a ,&b)&&(a != -1 && b != -1))
{
memset(line, 0 ,sizeof(line));
if(!a && !b)
{
printf("0\n");
continue;
}
C = R = 0;
while(a && b)
{
C = max(C , b);
R = max(R , a);
line[a][b] = 1;
scanf("%d %d",&a ,&b);
}
ans = 0;
for(int i = 1 ;i <= R ;i++)
for(int j = 1 ;j<=C ;j++)
if(line[i][j])
{
dfs(i,j);
ans++;
}
printf("%d\n" , ans);
}
return 0;
}