USACO Section 3.3 Home on the Range - 优化的BFS..
USACO 的数据也有很弱的阿..开始我的程序有个地方完全错了居然过了3个点...
我的思维:
首先很容易想到如果我能知道(x,y)为左上角边长为 t 的正方形满足条件(全为1)....那么我只要再扫下最右边的t+1个和最下面的t+1个就能知道(x,y)为左上角边长为 t +1的正方形是否还是满足全是1的要求..如果我能知道(x,y)为左上角边长为 t 的的正方形不满足条件(不全为1)...那么直接就能判断(x,y)为左上角边长为 t +1的正方形不满足全是1的要求...因为中间的那t*t个格子在前面就已经判断出来了..这里就利用了前面得到的结果..
那么可以首先将边长为2的手动判断出来并放到一个队列里去..队列里的node代表的就是满足条件的正方形..我这里存的就是正方形的左上角坐标和边长..后面要得出更大的正方形..从队列里取出一个正方形..拓展下右边和下边判断下是否满足..是就丢到队尾~~这样是可以得到所有要求的结果的..但是还是会超时..
这里想一下..当取出一个正方形..要将其右边一条和下面一条都扫一遍才知道是否能得出更大的正方形..这里在做的时候明显可能对一个点进行很多次判断是否为1..那么就要想办法更加利用前面扫描判断的结果..
用这个例子来想:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
如果要判断(1,1)为左上角..边长为4的正方形是否符合要求..首先通过(1,1)边长为3的正方形来进入了判断...如果是前面的思维..那么要扫描(1,4),(2,4),(3,4),(4,4),(4,1),(4,2),(4,3)才能确定(1,1)为左上角边长为4的正方形符合要求...但是我们在前面可以得出(2,2)边长为3的正方形是全1的..那么如果利用起来..那只要判断下(1,4)和(4,1)是否是1就ok了..如果(2,2)边长为3的正方形不全为1那也能马上得出(1,1)边长为4的正方形不满足全1...这一来..每次判断是否这个正方形满足..不管这个正方形边长为多少..只要3步就可以判断出结果.
所以要记录前面的结果...但又能发现在BFS时..要判断正方形满足条件只和其边长少1的正方形有关...所以还能用滚动数组来存正方形分布情况...又把空间从[250][250][250]降到了[2][250][250]...这道题就完美解决了..
Program:
/* ID: zzyzzy12 LANG: C++ TASK: range */ #include<iostream> #include<istream> #include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<algorithm> #include<queue> #define oo 1000000000 #define ll long long using namespace std; struct node { int x,y,t; }; struct node2 { bool s[260][260]; }can[2]; int n; bool arc[260][260]; queue<node> myqueue; bool getdata() { char c; c=getchar(); while (c!='1' && c!='0') c=getchar(); if (c=='1') return true; return false; } void getanswer() { int p,m,i,j,g=0; memset(can,false,sizeof(can)); node h,k; while (!myqueue.empty()) myqueue.pop(); p=2; m=0; for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (arc[i][j] && arc[i+1][j] && arc[i][j+1] && arc[i+1][j+1]) { k.y=i; k.x=j; k.t=2; can[g].s[i][j]=true; myqueue.push(k); } while (!myqueue.empty()) { h=myqueue.front(); myqueue.pop(); if (h.t!=p) { printf("%d %d\n",p,m); p=h.t; g=1-g; memset(can[1-g].s,false,sizeof(can[1-g].s)); m=1; }else m++; if (!can[g].s[h.y+1][h.x+1] || !arc[h.y+h.t][h.x] || !arc[h.y][h.x+h.t]) goto A; k=h; k.t=h.t+1; can[1-g].s[k.y][k.x]=true; myqueue.push(k); A: ; } if (m) printf("%d %d\n",p,m); return; } int main() { freopen("range.in","r",stdin); freopen("range.out","w",stdout); scanf("%d",&n); memset(arc,false,sizeof(arc)); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) arc[i][j]=getdata(); getanswer(); return 0; }