[URI ONLINE JUDGE] – 2067 – The Square Game

The “square game” is a very popular game nowadays! The game is very simple: you are given a grid with N lines and M columns containing non-negative integer numbers. The following image shows a grid with 3 lines and 4 columns.

You are also given an integer S. You must then choose some square with S lines and S columns contained entirely in the grid. Your score is given by the product of all integers inside the square you chose. For example, if S=2 and you decided to choose the square shown in blue in the given image, your score will be equal to 2×3×2×1 = 12.

You just realized that, depending on the square you choose, your score may be equal to zero. You are given a grid and a list of queries. For each query, you are given an integer S and must decide whether it is possible to choose a SxS square such that your score is not equal to zero.

Input

The first line contains two integers N and M (1 ≤ N, M ≤ 200) indicating the number of lines and columns of the grid. The next N lines contain M integers each, indicating the grid. Each integer in the grid is not greater than 109.

The next line contains an integer Q (1 ≤ Q ≤ 200) indicating the number of queries. Each of the next Q lines describes a query. Each line contains an integer S (1 ≤ S ≤ min(N,M)), the length of the square you must choose.

Output

For each query, print a single line containing yes if it is possible to choose a square such that your score is not equal to zero, or no otherwise.

Input Sample Output Sample
3 4
3 4 0 3
0 2 3 1
4 2 1 0
3
2
3
1
yes
no
yes

 

solution:

 

<br /> 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{

int n, m, q;
int grid[205][205];
int dp[205][205];
int maior = 0;
memset(dp, 0, sizeof dp);

cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> grid[i][j];
if(grid[i][j] == 0) {
dp[i][j] = 0;
} else {
dp[i][j] = min(dp[i-1][j-1],
min(dp[i-1][j], dp[i][j-1])) + 1;
maior = max(maior, dp[i][j]);
}
}
}

cin >> q;
while(q--) {
int t;
cin >> t;
if(t <= maior) printf("yes\n");
else printf("no\n");
}

return 0;
}

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s