UVa 559 Squares (II)
题目描述
题目模拟一个方格游戏。棋盘大小为h×wh \times wh×w（hhh行，www列），坐标(1,1)(1,1)(1,1)为左下角，(1,w)(1,w)(1,w)为右下角，(h,w)(h,w)(h,w)为右上角。玩家每次选择一个空闲方格，然后以其为左下角向右上方向扩展成一个最大可能的不与其他已占方格相交的正方形，并占据该正方形内的所有方格。给定已进行的若干步合法移动，要求找出下一步能形成的最大正方形的左下角坐标和边长。若有多个，选择rrr最小的；若仍相同，选择ccc最小的。
输入格式
第一行一个整数ggg，表示游戏数量。每个游戏第一行包含三个整数hhh、www、mmm（1≤h,w≤10001 \le h, w \le 10001≤h,w≤1000，0≤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−r+1r' = h - r + 1r′=h−r+1。
动态规划
定义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≤106，m≤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//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){intgames,h,w,m,dp[1100][1100]={0};intr,c,s;cin>>games;for(intg=1;g<=games;g++){cin>>h>>w>>m;for(inty=1;y<=h;y++){for(intx=1;x<=w;x++)dp[y][x]=1;dp[y][w+1]=0;}for(inti=1;i<=m;i++){cin>>r>>c;// translate coordinate.r=h-r+1;// find the maximum size of square at (r, c).for(inti=1;i<=r;i++)for(intj=w;j>=1;j--)if(dp[i][j])dp[i][j]=min(dp[i-1][j],min(dp[i-1][j+1],dp[i][j+1]))+1;// fill the occupied cell.s=dp[r][c];for(inty=0;y<s;y++)for(intx=0;x<s;x++)dp[r-y][c+x]=0;}// find the maximum size of square with smallest r and c.s=0;for(inti=1;i<=h;i++)for(intj=w;j>=1;j--)if(dp[i][j]){dp[i][j]=min(dp[i-1][j],min(dp[i-1][j+1],dp[i][j+1]))+1;if(s<dp[i][j]||(s==dp[i][j]&&(i>r||j<c))){s=dp[i][j];r=i,c=j;}}if(s==0)cout<<"game over\n";else{r=h-r+1;cout<<r<<' '<<c<<' '<<s<<'\n';}}return0;}