블루 브리지 컵 프로그램 설계 격자

8585 단어 프로그램 설계
우리는 그림의 빨간색 선을 따라 잘라서 두 부분을 얻었는데, 각 부분의 숫자와 모두 60이었다.
이 문제의 요구는 주어진 mxn의 칸에 있는 정수를 두 부분으로 나누어 이 두 구역의 숫자와 같게 할 수 있는지를 프로그래밍하여 판정하는 것이다.만약 여러 가지 해답이 존재한다면, 왼쪽 상단의 칸을 포함하는 그 구역에 포함된 칸의 최소 수를 출력하십시오.분할할 수 없는 경우 0 내보내기
 
프로그램 입력 출력 형식 요구 사항:
프로그램은 먼저 두 개의 정수 mn을 읽고 빈칸으로 나누기 (m, n<10) 는 표의 너비와 높이를 표시하고 그 다음은 n줄이며, 줄마다 m의 정수를 빈칸으로 나눈다.모든 정수는 10000프로그램 출력보다 크지 않습니다. 모든 해에서 왼쪽 상단을 포함하는 분할 구역은 최소한의 칸 수를 포함할 수 있습니다.
예: 사용자 입력: 3 310 1 5220 30 11 2 3
프로그램 출력: 3
예: 사용자 입력: 4 31 1 1 11 30 80 21 1 1 100
프로그램 출력: 10
자원 규약: 최대 메모리 소모 <64MCPU 소모 <5000ms
요구에 따라 엄격하게 출력하십시오. "입력하십시오."와 유사하게 출력하지 마십시오.라는 불필요한 내용을 담았다.
모든 코드를 같은 원본 파일에 놓고 디버깅이 통과되면 복사해서 이 원본 코드를 제출합니다.
주의:main 함수는 0 주의: ANSI C/ANSI C++ 표준만 사용하고 컴파일 환경이나 운영체제에 의존하는 특수 함수를 호출하지 마십시오.주의: 모든 의존 함수는 원본 파일에 #include를 명확하게 해야 하며, 프로젝트 설정을 통해 자주 사용하는 헤더 파일을 생략할 수 없습니다.
제출할 때 원하는 컴파일러 형식을 선택하십시오.
#include<stdio.h>

#include<string.h>

int a[11][11];

int isv[11][11];

//                  

int dx[4]={-1,0,1,0};

int dy[4]={0,-1,0,1};

int minStep;

int sum;

int n,m;

int is_ok(int x,int y,int num){

if(x<1 || x>m || y<1 || y>n)

return 0;

if(a[x][y]+num>sum/2)

return 0;

if(isv[x][y]==1)

return 0;

return 1;



}

//

void dfs(int x,int y,int num,int cnt){

//            ,            ,   

if(num==sum/2){

if(cnt+1<minStep)

minStep=cnt+1; //           

return;

}

for(int i=0;i<4;i++){ //

int nx=x+dx[i];

int ny=y+dy[i];

if(!is_ok(nx,ny,num)) //

continue;

isv[nx][ny]=1; //                    1 

dfs(nx,ny,num+a[nx][ny],cnt+1); //                

isv[nx][ny]=0;     //     ,      0,     

}

}

int main(){

//           

while(scanf("%d%d",&n,&m)==2){

//            

sum=0;

minStep=0x7fffffff;

//isv     ,              

memset(isv,0,sizeof(isv));

// 1             

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++){

scanf("%d",&a[i][j]);

sum+=a[i][j];

} 

//         ,      2 

if(sum%2){

printf("0
"); }else{ // isv[1][1]=1; dfs(1,1,a[1][1],0); printf("%d
",minStep); } } return 0; }

좋은 웹페이지 즐겨찾기