#include <stdio.h>
int d_table[1001][1001];
int table[1001][1001];
int down_table[1001][1001];
int right_table[1001][1001];
int n,m;
int max;
FILE *in=fopen("input.txt","r");
FILE *out=fopen("output.txt","w");
int s_min(int a,int b, int c){
int re_val = a;
if(re_val > b)
re_val = b;
if(re_val > c)
re_val = c;
return re_val;
}
int main(){
int i,j,t_in1,t_in2;
fscanf(in,"%d %d",&n,&m);
for(i=0;i<m;i++){
fscanf(in,"%d %d",&t_in1,&t_in2);
table[t_in1][t_in2] = 1;
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(table[i][j]==1){
down_table[i][j] = 0;
right_table[i][j] = 0;
}
else {
down_table[i][j] = down_table[i-1][j]+1;
right_table[i][j] = right_table[i][j-1]+1;
}
}
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
d_table[i][j] = s_min(down_table[i][j], right_table[i][j], d_table[i-1][j-1]+1);
if(d_table[i][j] > max)
max = d_table[i][j];
}
}
fprintf(out,"%d",max);
return 0;
}
'Programming' 카테고리의 다른 글
| 정사각형목장만들기 (0) | 2012/02/23 |
|---|---|
| Dijktra (3) | 2009/03/03 |
| [UVA 10000] Longest Paths (6) | 2007/07/26 |
| [UVA 10082] WERTYU (0) | 2007/07/26 |
| [UVA 10782] Send More Money (0) | 2007/07/26 |
| [PKU 1002] 487-3279 (2) | 2007/04/12 |
