uva 11067

BFS+DP

第一次用VIM寫忘記把freopen除掉 多了一堆錯誤

//====================================================================||
//                                                                    ||
//                                                                    ||
//                         Author : GCA                               ||
//                  6AE7EE02212D47DAD26C32C0FE829006                  ||
//====================================================================||
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\n")
#define I_de(x,n)for(int i=0;i<n;i++)printf("%d ",x[i]);Pln()
#define De(x)printf(#x"%d\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\
    printf("%2d ",dp[htx][hty]);}Pln();}
#define M 105
#define PII pair<int,int>
#define PB push_back
#define oo INT_MAX
#define Set_oo 0x3f
#define Is_debug true
#define debug(...) if(Is_debug)printf("DEBUG: "),printf(__VA_ARGS__)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
    int tmp=min(x,y);
    return min(tmp,z);
}
int max3(int x,int y,int z){
    int tmp=max(x,y);
    return max(tmp,z);
}
int w,h;
int n;
int mz[M][M];
Int used[M][M];
int dx[2]={0,1};
int dy[2]={1,0};
bool inq[M][M];
struct node{
    int x,y;
    node(int x,int y):x(x),y(y){};
    node(){};
};
void solve(){
    Set(inq,0);
    Set(used,0);
    queue<node> q;
    q.push(node(0,0));
    used[0][0]=1;
    inq[0][0]=1;
    while(!q.empty()){
///        for(int i=0;i<=h;i++){
///            for(int j=0;j<=w;j++){
///                printf("%2d ",used[j][i]);
///            }Pln();
///        }Pln();
        int x=q.front().x;
        int y=q.front().y;
        q.pop();
        Int u=used[x][y];
        for(int i=0;i<2;i++){
            int nex=x+dx[i],ney=y+dy[i];
            if(nex<0||nex>w||ney<0||ney>h)continue;
            if(mz[nex][ney])continue;
            used[nex][ney]+=u;
            if(!inq[nex][ney]){
                inq[nex][ney]=1;
                q.push(node(nex,ney));
            }
        }
        inq[x][y]=0;
    }
    if(used[w][h]==1){
        printf("There is one path from Little Red Riding Hood's house to her grandmother's house.\n");
    }else if(used[w][h]==0){
        printf("There is no path.\n");
    }else{
        printf("There are %lld paths from Little Red Riding Hood's house to her grandmother's house.\n"
                ,used[w][h]);
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    ios_base::sync_with_stdio(0);
    while(~scanf("%d%d",&w,&h)&&w+h){
        scanf("%d",&n);
        Set(mz,0);
        for(int i=0;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            mz[x][y]=1;
        }
        solve();
    }



    







}