A 扫地机
1.0 秒 131,072.0 KB 100 分
公司里用扫地机进行扫地，在扫地机进行扫地之前，我们先把一张公司的地图传送到扫地机里，地图用一个矩形网格表示，有垃圾的地方会被做一个标记。每一台扫地机从左上角开始，然后一直移动到右下角。扫地机只能向下或者向右移动。经过一个包含垃圾的格子时，扫地机就会把垃圾收集起来。扫地机移动到右下角之后就不会再移动了。现在给定一个地图，问最少要几台扫地机才能把地扫干净。
样例解释：
上图对应样例，下面两个图对应了两种方案，而第二种只需要两个扫地机。
输入
单组测试数据。
输入有若干行，每一行给出两个整数(x,y) ，(1<=x,y<=24)，表示垃圾所在的行和列，最后输入两个0表示输入结束。行和列的编号按照样例中的规则所示。没有两个点是重合的。
输出
输出一个整数表示答案。
输入样例
1 2
1 4
2 4
2 6
4 4
4 7
6 6
0 0
输出样例
2
#include<bits/stdc++.h>
using namespace std;
bool lj[31][31]={false};
int za=1,ans=0;
int x,y,mx=-1,my=-1;
int dg(int i,int j){
if(ans==0){
return za;
}
if(i==mx&&j==my){
za++;
dg(1,1);
}
else if(i==mx){
for(int m=j;m<=my;){
dg(i,j+1);
if(lj[i][j]==true){
lj[i][j]=false;
ans--;
}
}
}
else if(i==my){
for(int m=i;m<=mx;){
dg(i+1,j);
if(lj[i][j]==true){
lj[i][j]=false;
ans--;
}
}
}
else if(lj[i+1][j]==true&&lj[i][j+1]==false){
dg(i+1,j);
lj[i][j]=false;
ans--;
}
else if(lj[i][j+1]==true&&lj[i+1][j]==false){
dg(i,j+1);
lj[i][j]=false;
ans--;
}
else if(lj[i+1][j]==true&&lj[i][j+1]==true){
dg(i+1,j);
lj[i][j]=false;
ans--;
}
else if(lj[i+1][j]==false&&lj[i][j+1]==false){
dg(i,j+1);
}
}
int main(){
for(;;){
cin>>x>>y;
if(x==0&&y==0){
break;
}
ans++;
lj[x][y]=true;
mx=max(mx,x);
my=max(my,y);
}
cout<<0-dg(1,1)<<endl;
return 0;
}