【排序】绝境求生-白红宇

【排序】绝境求生

阅读量：5142 次

发布时间：2019-06-13

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

问题 E: 【排序】绝境求生

时间限制: 1 Sec

内存限制: 64 MB

提交: 4

解决: 4

[ ] [ ] [ ] [命题人:

]

题目描述

The Eight Puzzle, among other sliding-tile puzzles, is one of the famous problems in artificial intelligence. Along with chess, tic-tac-toe and backgammon, it has been used to study search algorithms.

The Eight Puzzle can be generalized into an M × N Puzzle where at least one of M and N is odd. The puzzle is constructed with MN − 1 sliding tiles with each a number from 1 to MN − 1 on it packed into a M by N frame with one tile missing. For example, with M = 4 and N = 3, a puzzle may look like:

Let's call missing tile 0. The only legal operation is to exchange 0 and the tile with which it shares an edge. The goal of the puzzle is to find a sequence of legal operations that makes it look like:

The following steps solve the puzzle given above.

Given an M × N puzzle, you are to determine whether it can be solved.

样例输入

3 31 0 34 2 57 8 64 31 2 54 6 911 8 103 7 00 0

样例输出

YESNO

分析：不知道之前什么时候水过这题，去POJ抄来了题解。。。一个树状数组求逆序对的题。。

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #define range(i,a,b) for(int i=a;i<=b;++i)#define LL long long#define rerange(i,a,b) for(int i=a;i>=b;--i)#define fill(arr,tmp) memset(arr,tmp,sizeof(arr))using namespace std;int n,m,tol,cnt,head[1000005],ans[1000005],tree[1000005],aa[1000005];void init(){}int sum(int x){ int sum=0; while(x>0){ sum+=tree[x]; x-=x&(-x); } return sum;}void add(int x,int y){ while(x<=1000005){ tree[x]+=y; x+=x&(-x); }}void solve(){ while(cin>>n>>m,n,m){ int x,y,t,s=0,num=0; range(i,1,n)range(j,1,m){ cin>>t; if(!t)x=i,y=j; else aa[num++]=t; } fill(tree,0); rerange(i,num-1,0){ s+=sum(aa[i]-1); add(aa[i],1); } if(m&1)cout<<(s&1?"NO":"YES")<

View Code

转载于:https://www.cnblogs.com/Rhythm-/p/9348674.html

你可能感兴趣的文章