// ===================================================================================== // // Filename: zoj2859.cpp // // Description: 2D RMQ -- Orz...卡了输出... // // Version: 1.0 // Created: 2012年03月02日 22时17分57秒 // Revision: none // Compiler: g++ // // Author: SphinX (Whisper), sphinx2010@yahoo.cn // Company: HFUT // // ===================================================================================== #include <iostream> #include <cstdlib> #include <cstdio> using namespace std; const int MAXN = 302; const int MAXK = 9; int test, n, m; int mtx[MAXN][MAXN], dp[MAXN][MAXN][MAXK][MAXK]; int pow_hash[MAXK], log_hash[MAXN]; void preproces() { log_hash[0] = 0; log_hash[1] = 0; for (int ind = 2, k = 1; ind < MAXN; ++ind) { if ((1 << (k + 1)) <= ind) { ++k; } log_hash[ind] = k; } for (int k = 0; (1 << k) < MAXN; ++k) { pow_hash[k] = (1 << k); } return ; } void initRMQ() { int k = log_hash[n]; for (int row = 0; row < n; ++row) { for (int col = 0; col < n; ++col) { dp[row][col][0][0] = mtx[row][col]; } } for (int i = 0; i <= k; ++i) { for (int j = 0; j <= k; ++j) { if (0 == i && 0 == j) { continue ; } for (int row = 0; row + pow_hash[i] <= n; ++row) { for (int col = 0; col + pow_hash[j] <= n; ++col) { if (0 == i) { dp[row][col][i][j] = min(dp[row][col][i][j - 1], dp[row][col + pow_hash[j - 1]][i][j - 1]); } else { dp[row][col][i][j] = min(dp[row][col][i - 1][j], dp[row + pow_hash[i - 1]][col][i - 1][j]); } } } } } return ; } int queryRMQ(int r1, int c1, int r2, int c2) { int kr = log_hash[r2 - r1 + 1]; int kc = log_hash[c2 - c1 + 1]; return min( min(dp[r1][c1][kr][kc], dp[r2 - pow_hash[kr] + 1][c2 - pow_hash[kc] + 1][kr][kc]), min(dp[r2 - pow_hash[kr] + 1][c1][kr][kc], dp[r1][c2 - pow_hash[kc] + 1][kr][kc]) ); } void ace() { int cas = 1; int r1, c1, r2, c2; preproces(); for (scanf("%d", &test); test--; ++cas) { scanf("%d", &n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &mtx[i][j]); } } initRMQ(); scanf("%d", &m); while (m--) { scanf("%d %d %d %d", &r1, &c1, &r2, &c2); printf("%d\n", queryRMQ(r1 - 1, c1 - 1, r2 - 1, c2 - 1)); } } return ; } int main(int argc, char *argv[]) { ace(); return EXIT_SUCCESS; }