UVa 559 Squares (II)

题目描述题目模拟一个方格游戏。棋盘大小为h×wh \times wh×whhh行www列坐标(1,1)(1,1)(1,1)为左下角(1,w)(1,w)(1,w)为右下角(h,w)(h,w)(h,w)为右上角。玩家每次选择一个空闲方格然后以其为左下角向右上方向扩展成一个最大可能的不与其他已占方格相交的正方形并占据该正方形内的所有方格。给定已进行的若干步合法移动要求找出下一步能形成的最大正方形的左下角坐标和边长。若有多个选择rrr最小的若仍相同选择ccc最小的。输入格式第一行一个整数ggg表示游戏数量。每个游戏第一行包含三个整数hhh、www、mmm1≤h,w≤10001 \le h, w \le 10001≤h,w≤10000≤m≤1000 \le m \le 1000≤m≤100。接下来mmm行每行两个整数rrr、ccc表示已选择的位置。输入保证移动合法。输出格式对于每个游戏输出一行若无合法移动输出game over否则输出三个整数rrr、ccc、sss表示最大正方形的左下角坐标和边长。样例输入2 8 8 4 8 1 3 6 1 4 2 1 500 1000 2 1 1 1 501输出5 2 4 game over题目分析本题的核心是动态规划计算最大全111正方形并支持更新标记已占方格为000。坐标转换输入坐标(r,c)(r, c)(r,c)中rrr从底部开始计数为方便处理转换为从顶部开始计数的坐标r′h−r1r h - r 1r′h−r1。动态规划定义dp[i][j]\textit{dp}[i][j]dp[i][j]表示以(i,j)(i, j)(i,j)为右下角的最大全111正方形边长。但本题需要以左下角为起点可以旋转视角或使用不同的 DP 方向。参考代码使用了从右下角向左上角更新的方式。更新已占方格每次移动后以该点为左下角扩展出最大正方形将该正方形内所有方格标记为已占000。查找最优解在所有空闲方格中找出能形成的最大正方形的边长。若边长相同选择rrr最小即原始坐标最小若rrr相同则选择ccc最小。复杂度分析h×w≤106h \times w \le 10^6h×w≤106m≤100m \le 100m≤100每次更新O(s2)O(s^2)O(s2)总可接受。代码实现// Squares (II)// UVa ID: 559// Verdict: Accepted// Submission Date: 2017-04-23// UVa Run Time: 0.880s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){intgames,h,w,m,dp[1100][1100]{0};intr,c,s;cingames;for(intg1;ggames;g){cinhwm;for(inty1;yh;y){for(intx1;xw;x)dp[y][x]1;dp[y][w1]0;}for(inti1;im;i){cinrc;// translate coordinate.rh-r1;// find the maximum size of square at (r, c).for(inti1;ir;i)for(intjw;j1;j--)if(dp[i][j])dp[i][j]min(dp[i-1][j],min(dp[i-1][j1],dp[i][j1]))1;// fill the occupied cell.sdp[r][c];for(inty0;ys;y)for(intx0;xs;x)dp[r-y][cx]0;}// find the maximum size of square with smallest r and c.s0;for(inti1;ih;i)for(intjw;j1;j--)if(dp[i][j]){dp[i][j]min(dp[i-1][j],min(dp[i-1][j1],dp[i][j1]))1;if(sdp[i][j]||(sdp[i][j](ir||jc))){sdp[i][j];ri,cj;}}if(s0)coutgame over\n;else{rh-r1;coutr c s\n;}}return0;}