最少步数

Dehydration · 2022-05-01 13:48:18 · 个人记录

#include<bits/stdc++.h>
using namespace std;
int s[9][9],a[9],b[9],cnt=2,n=8;
int book[9];
void bfs() {
    int head=0,tail=1;
    a[1]=1;
    b[1]=0;
    book[1]=1;
    do {
        head++;
        for(int i=1; i<=n; i++) {
            if(!s[a[head]][i]&&!book[i]) {
                tail++;
                a[tail]=i;
                b[tail]=head;
                book[i]=1;
                if(tail==n) {
                    cnt++;
                    head=tail;
                    break;
                }
            }
        }
    } while(head<tail);
    return;
}
int main() {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            cin >> s[i][j];
        }
    }
    bfs();
    cout << cnt;
    return 0;
}