블루 브리지 컵 프로그램 설계 격자
8585 단어 프로그램 설계
이 문제의 요구는 주어진 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
'좋은 코드/나쁜 코드 학습 디자인 입문'읽고 신경 쓴 일 노트총체적으로 말하자면, 대부분의 경우 '응, 그래' 에 동의할 수 있다. 또 앞으로'위험'과'주의(caution)'사이에 또 하나의 생명상태가 추가되는 상황에서 그것을 판단하는if문은 반드시 2행과 3행 사이에 틀리지...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.