博客

思路 : 这类棋盘搜索类问题, 初看起来, 感觉条件很多.状态转移无从下手. 我们可以把条件作为当前状态的一个属性.在每次DFS的时候把当前的这些状态的属性值作为参数传入进来.

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
int a[N][N], f[N][N];
int n, m;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int ans = 0x3f3f3f3f;
void dfs(int x, int y , int sum, bool flag) {

    if( 1 > x || 1 > y || x > n || y > n ) {
        return ;
    }
    if( f[x][y] <= sum ) {
        return ;
    }
    f[x][y] = sum;
    if(x == n && y == n) {
        ans = min(ans, sum);
        return ;
    }

    for(int i = 0 ; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if( a[xx][yy] ){
            if( a[x][y] == a[xx][yy]) {
                dfs(xx, yy, sum, false);
            } else {
                dfs(xx