奥特曼打怪兽
大概题意
在一个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;
}