小A和小B一起去电影院看电影，电影院的座位有N排，编号为1..N，每排有M个座位，编号为1..M，其中有些座位已经有人坐了。他们俩要找两个同一排相邻的两个无人的座位，问有多少个可行方案。
输入
三个整数N,M,K。
以下K行，每行两个数X，Y，表示第X排第Y个座位有人，同一个座位至多只出现一次。
输出
一个数，表示他们俩可以选择的方案数。
样例
输入1  
2 3 2
1 2
2 3
输出1  
1
输入2  
4 7 1
1 1
输出2  
23
提示
对于30%的数据，N,M<=100。
对于100%的数据，1<=N,M<=1,000,000,000，1<=K<=47。

请各位大神贴一下代码吧！！一点钟要交啊！
谢谢！

dfs、bfs，（我这个人打字相对较慢，就给点思路吧，实在不行再贴代码）

dfs相对这题简单。。。

既然是c++我就放开写了

写起来简单

#include<iostream>
using namespace std;
bool vis[100][100];
bool movie[100][100];
int ans;
int n,m,k;
void dfs(int x,int y){
    if(vis[x][y]==false){
        if(movie[x+1][y]==false&&vis[x+1][y]==false&&x!=n){
            ans++;
        }
        if(movie[x-1][y]==false&&vis[x+1][y]==false&&x!=0){
            ans++;
        }
        vis[x][y]=true;
    }
    if(x==n&&y!=m)dfs(0,y+1);
    else if(x==n&&y==m)return;
    else dfs(x+1,y);
}
int main(){
    cin>>n>>m>>k;
    int a,b;
    for(int i=0;i<k;++i){
        cin>>a>>b;
        movie[a-1][b-1]=true;
    }
    /*
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<movie[i][j];
        }
        cout<<"\n";
    }
    */
    dfs(0,0);
    cout<<ans;
    return 0;
}

注意

我还不懂对于百分之几的数据的意义何在