특수 행렬 연산

문제 설명: 행렬에 특정한 특수 연산이 존재한다고 가정하고 행렬의 임의의 요소에 대해 1을 줄여야 할 때 이웃(위 아래 좌우) 중 하나를 동시에 1을 줄여야 한다.현재 하나의 행렬을 지정하여 유한한 특수 연산을 통해 제로 행렬을 얻을 수 있는지 판단하도록 요구하다
사고방식: 거슬러 올라가는 법.특수한 연산을 할 수 있는 모든 위치를 일일이 열거하여 귀속시키고, 원소가 0보다 작은 상황이 발생하면 거슬러 올라간다.매번 0 행렬을 판단하지 않고 계수 변수 cnt를 유지하고 현재 행렬의 비 0 원소 개수를 통계합니다.특수 연산을 진행할 때마다 cnt의 값을 업데이트합니다
코드(효율이 낮으므로 더욱 최적화할 수 있어야 함):
int ok;  // , 

void process(int ** a, int n, int m, int cnt){
	if(cnt == 0) ok = 1;
	else{
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(a[i][j]-1 >= 0){  // 
					a[i][j]--;
					if(i-1 >= 0 && a[i-1][j]-1 >= 0){
						a[i-1][j]--;
						if(a[i][j] == 0 && a[i-1][j] == 0) process(a, n, m, cnt-2);
						else if(a[i][j]*a[i-1][j] == 0 && a[i][j]+a[i-1][j] != 0) process(a, n, m, cnt-1);
						else process(a, n, m, cnt);
						a[i-1][j]++;
					}
					if(i+1 < n && a[i+1][j]-1 >= 0){
						a[i+1][j]--;
						if(a[i][j] == 0 && a[i+1][j] == 0) process(a, n, m, cnt-2);
						else if(a[i][j]*a[i+1][j] == 0 && a[i][j]+a[i+1][j] != 0) process(a, n, m, cnt-1);
						else process(a, n, m, cnt);
						a[i+1][j]++;
					}
					if(j-1 >= 0 && a[i][j-1]-1 >= 0){
						a[i][j-1]--;
						if(a[i][j] == 0 && a[i][j-1] == 0) process(a, n, m, cnt-2);
						else if(a[i][j]*a[i][j-1] == 0 && a[i][j]+a[i][j-1] != 0) process(a, n, m, cnt-1);
						else process(a, n, m, cnt);
						a[i][j-1]++;
					}
					if(j+1 < m && a[i][j+1]-1 >= 0){
						a[i][j+1]--;
						if(a[i][j] == 0 && a[i][j+1] == 0) process(a, n, m, cnt-2);
						else if(a[i][j]*a[i][j+1] == 0 && a[i][j]+a[i][j+1] != 0) process(a, n, m, cnt-1);
						else process(a, n, m, cnt);
						a[i][j+1]++;
					}
					a[i][j]++;  // 
				}
			}
		}
	}
}

좋은 웹페이지 즐겨찾기