递推求解飞行员兄弟(c++实现)

2024-01-03 19:27:41
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 6;
char s[N][N],backup[N][N];
int dx[13] = {0,0,0,0,1,2,3,-1,-2,-3,0,0,0},dy[13]={0,1,2,3,0,0,0,0,0,0,-1,-2,-3};

int get(int x, int y)
{
    return x * 4 + y;
}


void turn(int x, int y) {
    for (int i = 0; i < 13; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < 4 && b >= 0 && b < 4) {
            if (s[a][b] == '-') s[a][b] = '+';
            else s[a][b] = '-';
        }
    }
}
int main(){
    for(int i=0;i<4;i++) scanf("%s",s[i]);
    vector<pair<int,int>> res;
    for (int op = 0; op < 1 << 16; op ++ )
    {
        vector<pair<int,int>> tmp;
        memcpy(backup, s, sizeof s);        // 备份

        for (int i = 0; i < 4; i ++ )
            for (int j = 0; j < 4; j ++ )
                if (op >> get(i, j) & 1)
                {
                    tmp.push_back({i+1, j+1});
                    turn(i, j);
                }

        bool success = true;
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                if(s[i][j] == '+'){
                    success = false;
                    break;
                }
            }
        }
        if(success) {
            if(res.empty() || res.size() > tmp.size())
                res = tmp;
        }
        memcpy(s,backup,sizeof backup);
    }
    int len = res.size();
    printf("%d\n",len);
    for(auto path : res) printf("%d %d\n",path.first,path.second);
}

文章来源:https://blog.csdn.net/zyang654321/article/details/135324389
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。