注册 登录
编程论坛 C语言论坛

C++ Movie

Jason_ 发布于 2020-03-22 10:47, 1967 次点击
小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。
8 回复
#2
Jason_2020-03-22 12:38
请各位大神贴一下代码吧!!一点钟要交啊!
谢谢!
#3
return_02020-03-22 18:22
dfs、bfs,(我这个人打字相对较慢,就给点思路吧,实在不行再贴代码)
#4
return_02020-03-22 18:25
dfs相对这题简单。。。
#5
return_02020-03-22 18:26
既然是c++我就放开写了
#6
return_02020-03-22 18:27
写起来简单
#7
return_02020-03-22 18:44
程序代码:
#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;
}
#8
lin51616782020-03-23 02:08
回复 7楼 return_0
注意
对于100%的数据,1<=N,M<=1,000,000,000,1<=K<=47。
#9
maomao123452020-03-24 10:27
我还不懂对于百分之几的数据的意义何在
1