[蓝桥杯][2013年第四届真题]剪格子

一定要好好审题啊！！！行号和列号跟题意要求的搞反了，结果de到怀疑人生了。。。

这个题给的数据量不大，所以我就放心大胆的在每个中间节点里各开了一个vis标记数组，用来记录每一条广搜路径走过的节点。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <string>
#include <map>
#include <stack>
#define MAXN 12
#define MOD 1000000009
#define INF 0x7ffffff
#define lowbit(x) (x)&(-x)

using namespace std;

int n,m;
int edge[MAXN][MAXN];
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
int sum;

struct Node{
    int x,y;
    int vis[MAXN][MAXN];
    int sum;
    int step;
    Node(int x,int y,int sum,int step):x(x),y(y),sum(sum),step(step){
        memset(vis,0,sizeof(vis));
    }
    Node(){}
};

queue<Node> que;

int BFS(int x,int y){
    Node head(x,y,edge[x][y],1);
    head.vis[x][y] = 1;
    que.push(head);
    while(!que.empty()){
        head = que.front();
        que.pop();
        if(head.sum == sum/2){
            return head.step;
        }
        for(int i=0;i<4;++i){
            int tx = head.x + dir[i][0];
            int ty = head.y + dir[i][1];
            if(tx < 0 || tx >= n || ty < 0 || ty >= m || head.vis[tx][ty]) continue;
            Node node(tx,ty,head.sum+edge[tx][ty],head.step+1);
            memcpy(node.vis,head.vis,sizeof(head.vis));
            node.vis[tx][ty] = 1;
            que.push(node);
        }
    }
    return 0;
}

inline void init(){
    sum = 0;
    while(!que.empty()) que.pop();
}

int main(){
    while(cin >> m >> n){
        init();
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                cin >> edge[i][j];
                sum += edge[i][j];
            }
        }
        if(sum&1) cout << 0 << endl;
        else cout << BFS(0,0) << endl;
    }
    return 0;
}