本文主要是介绍cf1228B B. Filling the Grid，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Suppose there is a ℎ×? grid consisting of empty or full cells. Let’s make some definitions:
?? is the number of consecutive full cells connected to the left side in the ?-th row (1≤?≤ℎ). In particular, ??=0 if the leftmost cell of the ?-th row is empty.
?? is the number of consecutive full cells connected to the top end in the ?-th column (1≤?≤?). In particular, ??=0 if the topmost cell of the ?-th column is empty.
In other words, the ?-th row starts exactly with ?? full cells. Similarly, the ?-th column starts exactly with ?? full cells.
These are the ? and ? values of some 3×4 grid. Black cells are full and white cells are empty.
You have values of ? and ?. Initially, all cells are empty. Find the number of ways to fill grid cells to satisfy values of ? and ?. Since the answer can be very large, find the answer modulo 1000000007(109+7). In other words, find the remainder after division of the answer by 1000000007(109+7).
Input
The first line contains two integers ℎ and ? (1≤ℎ,?≤103) — the height and width of the grid.
The second line contains ℎ integers ?1,?2,…,?ℎ (0≤??≤?) — the values of ?.
The third line contains ? integers ?1,?2,…,?? (0≤??≤ℎ) — the values of ?.
Output
Print the answer modulo 1000000007(109+7).
Examples
inputCopy
3 4
0 3 1
0 2 3 0
outputCopy
2
inputCopy
1 1
0
1
outputCopy
0
inputCopy
19 16
16 16 16 16 15 15 0 5 0 4 9 9 1 4 4 0 8 16 12
6 12 19 15 8 6 19 19 14 6 9 16 10 11 15 4
outputCopy
797922655
Note
In the first example, this is the other possible case.
In the second example, it’s impossible to make a grid to satisfy such ?, ? values.
In the third example, make sure to print answer modulo (109+7).
被Hack了，一场掉灰。。。
记得考虑不成立的情况
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>using namespace std;typedef long long ll;
const ll maxn = 1e3 + 7;
const ll mod = 1e9 + 7;
ll r[maxn],c[maxn];
ll maze[maxn][maxn];ll p[1000007];void init()
{p[0] = 1;for(ll i = 1;i <= 1000000;i++){p[i] = p[i - 1] * 2 % mod;}
}int main()
{ll h,w;scanf("%lld%lld",&h,&w);for(ll i = 1;i <= h;i++){scanf("%lld",&r[i]);}for(ll i = 1;i <= w;i++){scanf("%lld",&c[i]);}memset(maze,-1,sizeof(maze));for(ll i = 1;i <= h;i++){if(r[i] == 0){maze[i][1] = 0;}else{for(ll j = 1;j <= r[i];j++){maze[i][j] = 1;}}}for(ll i = 1;i <= w;i++){if(c[i] == 0){maze[1][i] = 0;}else{for(ll j = 1;j <= c[i];j++){maze[j][i] = 1;}}}for(int i = 1;i <= h;i++){if(r[i] == 0){if(maze[i][1] != 0){printf("0\n");return 0;}}else{int tmp = 0;for(int j = 1;j <= w;j++){if(maze[i][j] != 1)break;tmp++;if(tmp > r[i]){printf("0\n");return 0;}}if(tmp < r[i]){printf("0\n");return 0;}}}for(int i = 1;i <= w;i++){if(c[i] == 0){if(maze[1][i] != 0){printf("0\n");return 0;}}else{int tmp = 0;for(int j = 1;j <= h;j++){if(maze[j][i] != 1)break;tmp++;if(tmp > c[i]){printf("0\n");return 0;}}if(tmp < c[i]){printf("0\n");return 0;}}}ll cnt = 0;for(ll i = 1;i <= h;i++){for(ll j = 1;j <= w;j++){if(maze[i][j] == -1){ll flag1 = 0,flag2 = 0;for(ll ci = i - 1;ci >= 1;ci--){if(maze[ci][j] == -1 || maze[ci][j] == 0){flag1 = 1;break;}}for(ll cj = j - 1;cj >= 1;cj--){if(maze[i][cj] == -1 || maze[i][cj] == 0){flag2 = 1;break;}}if(flag1 && flag2)cnt++;}}}init();printf("%lld\n",p[cnt]);return 0;
}
这篇关于cf1228B B. Filling the Grid的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
