#include <stdio.h>
int data[2224][2224]; /** 입력배열 **/
struct m1 /** main **/
{
unsigned int n;
int x;
int y;
unsigned int money;
} m[1000000];
struct s1 /** sub **/
{
unsigned int n;
int x;
int y;
unsigned int money;
int type;
} s[1000000];
int main()
{
/*
FILE *in=fopen("input.txt","r");
FILE *out=fopen("output.txt","w");
*/
int i,j,n,mcnt=0,scnt=0;
unsigned int min=99999999;
int c=0,c1=0;
scanf("%d\n",&n);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
scanf("%d ",&data[i][j]);
}
}
mcnt=1;
m[0].x=1;
m[0].y=1;
m[0].n=data[1][1];
do
{
scnt=0;
for(i=0; i<mcnt; i++)
{
/** 조건 4 **/
if(m[i].x==n && m[i].y==n)
{
if(m[i].money<min) min=m[i].money;
continue;
}
/** 조건 1 **/
if(m[i].x<n && m[i].y<n)
{
if(m[i].y!=n)
{
if(m[i].n>data[m[i].x][m[i].y+1])
{
s[scnt].x=m[i].x;
s[scnt].y=m[i].y+1;
s[scnt].n=data[m[i].x][m[i].y+1];
s[scnt].money=m[i].money;
s[scnt].type=0;
scnt++;
}
else
{
s[scnt].x=m[i].x;
s[scnt].y=m[i].y;
s[scnt].n=m[i].n+1;
s[scnt].money=m[i].money+1;
s[scnt].type=1;
scnt++;
}
}
if(m[i].x!=n)
{
if(m[i].n>data[m[i].x+1][m[i].y])
{
s[scnt].x=m[i].x+1;
s[scnt].y=m[i].y;
s[scnt].n=data[m[i].x+1][m[i].y];
s[scnt].money=m[i].money;
s[scnt].type=0;
scnt++;
}
else
{
s[scnt].x=m[i].x;
s[scnt].y=m[i].y;
s[scnt].n=m[i].n+1;
s[scnt].money=m[i].money+1;
s[scnt].type=1;
scnt++;
}
}
}
else if(m[i].x==n && m[i].y<n) /**조건 2 **/
{
if(m[i].y!=n)
{
if(m[i].n>data[m[i].x][m[i].y+1])
{
s[scnt].x=m[i].x;
s[scnt].y=m[i].y+1;
s[scnt].n=data[m[i].x][m[i].y+1];
s[scnt].money=m[i].money;
s[scnt].type=0;
scnt++;
}
else
{
s[scnt].x=m[i].x;
s[scnt].y=m[i].y;
s[scnt].n=m[i].n+1;
s[scnt].money=m[i].money+1;
s[scnt].type=1;
scnt++;
}
}
}
else /** 조건 3 **/
{
if(m[i].x!=n)
{
if(m[i].n>data[m[i].x+1][m[i].y])
{
s[scnt].x=m[i].x+1;
s[scnt].y=m[i].y;
s[scnt].n=data[m[i].x+1][m[i].y];
s[scnt].money=m[i].money;
s[scnt].type=0;
scnt++;
}
else
{
s[scnt].x=m[i].x;
s[scnt].y=m[i].y;
s[scnt].n=m[i].n+1;
s[scnt].money=m[i].money+1;
s[scnt].type=1;
scnt++;
}
}
}
}
if(scnt==0) break;
mcnt=0;
for(i=0; i<scnt; i++)
{
c=0;
for(j=0; j<i; j++)
{
if(s[j].x==s[i].x && s[j].y==s[i].y && s[j].money<=s[i].money)
{
c=1;
break;
}
}
if(c==0 && s[i].type==0)
{
m[mcnt].x=s[i].x;
m[mcnt].y=s[i].y;
m[mcnt].n=data[s[i].x][s[i].y];
m[mcnt].money=s[i].money;
mcnt++;
}
else if(c==0 && s[i].type==1)
{
m[mcnt].x=s[i].x;
m[mcnt].y=s[i].y;
m[mcnt].n=s[i].n;
m[mcnt].money=s[i].money;
mcnt++;
}
}
}
while(1);
printf("%d",min);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 2 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 3 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 4 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 5 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 6 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 7 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 8 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 9 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 10 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 11 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 12 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 13 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 14 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 15 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 16 |
Correct |
0 ms |
55564 KB |
Output is correct |
| 17 |
Correct |
0 ms |
55564 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
55564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2000 ms |
55560 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2000 ms |
55560 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
