【华为机试题解】奥特曼打怪兽

大概题意

在一个N*N的正方形区域，每个小格可能有三种状态
值为0，正常可通过
值为1，奥特曼可通过，同时还可以消灭怪兽，消灭后值变为0，消灭怪兽数量+1
值为-1，有大石头，奥特曼无法通过

奥特曼需要先从上往下走，这个过程只能向下或者向右，到达右下角后，再从下往上走，这个过程只能向左或向上。需要找到奥特曼可以消灭怪兽的最大数量

输入：
第一行一个N，表示N的正方形区域的大小，N不超过50
第二行到N+1行，每一行N个数，表示正方形区域的情况

输出：
奥特曼可以消灭怪兽的最大数量

思路

1、和以前的动态规划很像，但是好像是不能用动态规划。（leetcode 741打脸了）
2、回溯，本题给C++的时间是2秒，一般都是1秒，说明可以走高复杂度策略

心情

考试的时候没写出来，考完后写出来了，就是这种心情

代码

#include <bits/stdc++.h>
using namespace std;
const int MAX = 60;

void walkup(int gird[MAX][MAX], int i, int j, int N, int tempAns, int& trueAns){
	if(i == 0 && j == 0){
		if(trueAns < tempAns){
			trueAns = tempAns;
		}
	}
	else if(i == 0){
		if(gird[i][j] == 0){
			walkup(gird, i, j-1, N, tempAns, trueAns);
		}
		else if(gird[i][j] == 1){
			gird[i][j] = 0;
			walkup(gird, i, j-1, N, tempAns+1, trueAns);
			gird[i][j] = 1;
		}
	}
	else if(j == 0){
		if(gird[i][j] == 0){
			walkup(gird, i-1, j, N, tempAns, trueAns);
		}
		else if(gird[i][j] == 1){
			gird[i][j] = 0;
			walkup(gird, i, j-1, N, tempAns+1, trueAns);
			gird[i][j] = 1;
		}
	}
	else{
		if(gird[i][j] == 0){
			walkup(gird, i-1, j, N, tempAns, trueAns);
			walkup(gird, i, j-1, N, tempAns, trueAns);
		}
		else if(gird[i][j] == 1){
			gird[i][j] = 0;
			walkup(gird, i-1, j, N, tempAns+1, trueAns);
			walkup(gird, i, j-1, N, tempAns+1, trueAns);
			gird[i][j] = 1;
		}
	}
}


void walkdown(int gird[MAX][MAX], int i, int j, int N, int tempAns, int& trueAns){
	if(i == N-1 && j == N-1){
		if(gird[i][j] == 0){
			walkup(gird, i-1, j, N, tempAns, trueAns);
			walkup(gird, i, j-1, N, tempAns, trueAns);
		}
		else if(gird[i][j] == 1){
			walkup(gird, i-1, j, N, tempAns+1, trueAns);
			walkup(gird, i, j-1, N, tempAns+1, trueAns);
		}
	}
	else if(i == N-1){
		if(gird[i][j] == 0){
			walkdown(gird, i, j+1, N, tempAns, trueAns);
		}
		else if(gird[i][j] == 1){
			gird[i][j] = 0;
			walkdown(gird, i, j+1, N, tempAns+1, trueAns);
			gird[i][j] = 1;
		}
	}
	else if(j == N-1){
		if(gird[i][j] == 0){
			walkdown(gird, i+1, j, N, tempAns, trueAns);
		}
		else if(gird[i][j] == 1){
			gird[i][j] = 0;
			walkdown(gird, i+1, j, N, tempAns+1, trueAns);
			gird[i][j] = 1;
		}
	}
	else{
		if(gird[i][j] == 0){
			walkdown(gird, i+1, j, N, tempAns, trueAns);
			walkdown(gird, i, j+1, N, tempAns, trueAns);
		}
		else if(gird[i][j] == 1){
			gird[i][j] = 0;
			walkdown(gird, i+1, j, N, tempAns+1, trueAns);
			walkdown(gird, i, j+1, N, tempAns+1, trueAns);
			gird[i][j] = 1;
		}
	}
}

int main()
{
	int gird[MAX][MAX];
	int dp[MAX][MAX];
	for(int i = 0; i < MAX; i++){
		for(int j = 0; j < MAX; j++){
			gird[i][j] = 0;
			dp[i][j] = 0;
		}
	}
	int N;
	cin >> N;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cin >> gird[i][j];
		}
	}
	
	// 从上往下走
//	for(int i = 0; i < N; i++){
//		for(int j = 0; j < N; j++){
//			if(gird[i][j] == 0){
//				dp[i][j] = dp[i][j-1] > dp[i-1][j] ? dp[i][j-1] : dp[i-1][j];
//			}
//			else if(gird[i][j] == 1){
//				dp[i][j] = dp[i][j-1] > dp[i-1][j] ? dp[i][j-1] : dp[i-1][j];
//				dp[i][j]++;
//			}
//			else{
//				dp[i][j] = -1;
//			}
//		}
//	}
	
	int tempAns = 0;
	int trueAns = 0;
	walkdown(gird, 0, 0, N, tempAns, trueAns);
	cout << trueAns << endl;
	
	return 0;
}