Codeforce 369D. Valera and Fools

[BFS、dijkstra]
反正狀態只長醬子
[有].....[有.....有]
N^2狀態

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
#define NN 3010
#define INF 4000
int prob[NN];
int Status[NN][NN];
struct ST{int x,y;};
ST newST(int a,int b)
{
    ST re;re.x=a,re.y=b;
    return re;
}
deque<ST> BFS;
bool vempty=false;
int cnt=1;
void visit(int a,int b,int k)
{
    //printf("visit(%d,%d)\n",a,b);
    //if(b<=-1) return;
    if(Status[a][b]>k)
    {
        //printf("PP");
        if(Status[a][b]==INF)
            cnt++;
        Status[a][b]=k;
        BFS.push_back(newST(a,b));
    }
}
int main()
{
    BFS.clear();
    int n,k;
    int Dead_ptr,Undead_ptr;
    scanf("%d %d",&n,&k);
    for(int lx=0;lx<=n;lx++)
        for(int ly=0;ly<=n;ly++)
            Status[lx][ly]=INF;
    Dead_ptr=0;
    Undead_ptr=n+1;
    for(int lx=1;lx<=n;lx++)
    {
        scanf("%d",prob+lx);
        if(prob[lx]==100)
            Dead_ptr=lx;
    }
    for(int lx=n;(prob[lx]==0)&&lx;lx--)
        Undead_ptr=lx;
    BFS.push_back(newST(n,n-1));
    Status[n][n-1]=0;
    while(BFS.size())
    {
        ST out=BFS.front();
        BFS.pop_front();
         int ptr1=n-out.x+1;
        if(Status[out.x][out.y]>=k) break;
        if((n-out.y+1)>=Undead_ptr)
        {
            if(prob[ptr1]>0)
                visit(out.x,out.y-1,Status[out.x][out.y]+1);
            continue;
        }
        if(out.y==0) continue;

        if(prob[ptr1]>0)    //兩隻同時死掉
        {
            if(out.y==1)
                vempty=true;
            else
                visit(out.y-1,out.y-2,Status[out.x][out.y]+1);
        }
        if(prob[ptr1]<100)
            visit(out.y,out.y-1,Status[out.x][out.y]+1);
        if(n-out.x+1<Dead_ptr) continue;
        if(prob[ptr1]>0)
            visit(out.x,out.y-1,Status[out.x][out.y]+1);
    }
    printf("%d\n",cnt+vempty);
    return 0;
}