poj1548Robots dfs实践

//搜索每一行
//该生产线的整点已被清除
//然后位置，然后转移到下一个步走的最后一点
//然后，所有点的下面一行清晰
//然后重复上面的操作
#include<iostream>
#include<cstdio>
#include<cstring>
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 ");
            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 " , ans);
    }
    return 0;
}

版权声明：本文博客原创文章，博客，未经同意，不得转载。