2017 ACM-ICPC 南宁区比赛 Minimum Distance in a Star Graph-白红宇

2017 ACM-ICPC 南宁区比赛 Minimum Distance in a Star Graph

阅读量：4971 次

发布时间：2019-06-12

本文共 974 字，大约阅读时间需要 3 分钟。

2017-09-25 19:58:04

writer：pprp

题意看上去很难很难，但是耐心看看还是能看懂的，给你n位数字

你可以交换第一位和之后的某一位，问你采用最少的步数可以交换成目标

有五组数据

用BFS进行搜索，并进行剪枝，已经搜索过的点不再搜索

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;string sa, sb;int n;struct node{ string str; int times; node() { str = ""; times = 0; }};int bfs(){ queue
            
              q; set
             
               ss; node now , nex; now.str = sa; q.push(now); ss.insert(now.str); while(!q.empty()) { now = q.front(); q.pop(); if(now.str == sb) return now.times; for(int i = 1; i < n;i++) { nex.str = now.str; nex.times = now.times+1; nex.str[i] = now.str[0]; nex.str[0] = now.str[i]; if(ss.count(nex.str) == 0) { ss.insert(nex.str); q.push(nex); } else continue; } }}int main(){ cin >> n; for(int i = 0 ; i < 5 ;i++) { cin >> sa >> sb; cout << bfs() << endl; } return 0;}