必威体育Betway必威体育官网
当前位置:首页 > IT技术

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

时间:2019-10-06 06:43:24来源:IT技术作者:seo实验室小编阅读:52次「手机版」
 

奥特曼打怪兽

大概题意

在一个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;
}

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读