Участник:Andriygav/ALICECUB

Материал из DISCOPAL
Перейти к: навигация, поиск
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
 
int visited[131072];
// сразу выпишем все ребра в графе
int list[17][4]={2, 3, 9, 5,
                 1, 10, 4, 6,
                 11, 1, 7, 4,
                 2, 8, 12, 3,
                 13, 1, 6, 7,
                 5, 14, 2, 8,
                 15, 5, 3, 8,
                 16, 6, 7, 4,
                 13, 1, 11, 10,
                 9, 2, 14, 12,
                 15, 9, 3, 12,
                 4, 10, 11, 16,
                 5, 14, 15, 9,
                 16, 13, 10, 6,
                 7, 16, 13, 11,
                 15, 14, 8, 12};
 
void bfs(int state, int k){
    int x, make;
    visited[state] = k;
 
    // рекурсия не проходит по времени, поэтому пришлось разворачивать рекурсию
    queue<int> q;
    q.push(state);
    while(!q.empty()){
        state = q.front();
        q.pop();
 
        if(visited[state] == 3){
            return;
        }
 
        for(int i = 0; i < 16; i++){
            if((state & (1 << i)) == 0){
                continue;
            }
            for(int j = 0; j < 4; j++){
                x = list[i][j];
                if((state & (1 << (x - 1))) != 0){
                    continue;
                }
                make = state;
                make ^= (1 << i);
                make ^= (1 << (x - 1));
                if(visited[make] == -1){
                    visited[make] = visited[state] + 1;
                    q.push(make);
                }
            }
        }    
    }
}
 
int main(){
    memset(visited, -1, sizeof(visited));
    // сразу пройдемся по всему графу
    bfs(65280, 0);
 
    int t;
    cin >> t;
    for(int j = 1; j <= t; j++){
        int state = 0;
        for(int i = 0; i < 16; i++){
            int x;
            cin >> x;
            state |= (x << i);
        }
 
        cout << "Case #" << j << ": ";
        if(visited[state] != -1 && visited[state] <= 3){
            cout << visited[state] << endl;
        }else{
            cout << "more" << endl;
        }
    }
    return 0;
}