首页 > > 程序设计 > C/C++ >

POJ 2983 M × N Puzzle

2018-12-27 07:40:48来源：博客园阅读 ()

M × N Puzzle

Time Limit: 4000MS		Memory Limit: 131072K
Total Submissions: 4860		Accepted: 1321

Description

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 toMN ? 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:

1	6	2
4	0	3
7	5	9
10	8	11

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:

1	2	3
4	5	6
7	8	9
10	11	0

The following steps solve the puzzle given above.

START

1	6	2
4	0	3
7	5	9
10	8	11

DOWN
?

1	0	2
4	6	3
7	5	9
10	8	11

LEFT
?

1	2	0
4	6	3
7	5	9
10	8	11

UP
?

1	2	3
4	6	0
7	5	9
10	8	11

…

RIGHT
?

1	2	3
4	0	6
7	5	9
10	8	11

UP
?

1	2	3
4	5	6
7	0	9
10	8	11

UP
?

1	2	3
4	5	6
7	8	9
10	0	11

LEFT
?

1	2	3
4	5	6
7	8	9
10	11	0

GOAL

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

Input

The input consists of multiple test cases. Each test case starts with a line containing M and N (2 ≤ M, N ≤ 999). This line is followed by M lines containing N numbers each describing an M × N puzzle.

The input ends with a pair of zeroes which should not be processed.

Output

Output one line for each test case containing a single word YES if the puzzle can be solved and NO otherwise.

Sample Input

3 3 1 0 3 4 2 5 7 8 6 4 3 1 2 5 4 6 9 11 8 10 3 7 0 0 0

Sample Output

YES NO

  1 #include<cstdio>
  2 //#include<iostream>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<vector>
  7 //#include<queue>
  8 //#include<set>
  9 #define INF 0x3f3f3f3f
 10 #define N 10000005
 11 #define re register
 12 #define Ii inline int
 13 #define Il inline long long
 14 #define Iv inline void
 15 #define Ib inline bool
 16 #define Id inline double
 17 #define ll long long
 18 #define Fill(a,b) memset(a,b,sizeof(a))
 19 #define R(a,b,c) for(register int a=b;a<=c;++a)
 20 #define nR(a,b,c) for(register int a=b;a>=c;--a)
 21 #define Min(a,b) ((a)<(b)?(a):(b))
 22 #define Max(a,b) ((a)>(b)?(a):(b))
 23 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))
 24 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))
 25 #define D_e(x) printf("\n&__ %d __&\n",x)
 26 #define D_e_Line printf("-----------------\n")
 27 #define D_e_Matrix for(re int i=1;i<=n;++i){for(re int j=1;j<=m;++j)printf("%d ",g[i][j]);putchar('\n');}
 28 using namespace std;
 29 //    The Code Below Is Bingoyes's Function Forest.
 30 
 31 Ii read(){
 32     int s=0,f=1;char c;
 33     for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
 34     while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();
 35     return s*f;
 36 }
 37 Iv print(ll x){
 38     if(x<0)putchar('-'),x=-x;
 39     if(x>9)print(x/10);
 40     putchar(x%10^'0');
 41 }
 42 /*
 43 Iv Floyd(){
 44     R(k,1,n)
 45         R(i,1,n)
 46             if(i!=k&&dis[i][k]!=INF)
 47                 R(j,1,n)
 48                     if(j!=k&&j!=i&&dis[k][j]!=INF)
 49                         Cmin(dis[i][j],dis[i][k]+dis[k][j]);
 50 }
 51 Iv Dijkstra(int st){
 52     priority_queue<int>q;
 53     R(i,1,n)dis[i]=INF;
 54     dis[st]=0,q.push((nod){st,0});
 55     while(!q.empty()){
 56         int u=q.top().x,w=q.top().w;q.pop();
 57         if(w!=dis[u])continue;
 58         for(re int i=head[u];i;i=e[i].nxt){
 59             int v=e[i].pre;
 60             if(dis[v]>dis[u]+e[i].w)
 61                 dis[v]=dis[u]+e[i].w,q.push((nod){v,dis[v]});
 62         }
 63     }
 64 }
 65 Iv Count_Sort(int arr[]){
 66     int k=0;
 67     R(i,1,n)
 68         ++tot[arr[i]],Cmax(mx,a[i]);
 69     R(j,0,mx)
 70         while(tot[j])
 71             arr[++k]=j,--tot[j];
 72 }
 73 Iv Merge_Sort(int arr[],int left,int right,int &sum){
 74     if(left>=right)return;
 75     int mid=left+right>>1;
 76     Merge_Sort(arr,left,mid,sum),Merge_Sort(arr,mid+1,right,sum);
 77     int i=left,j=mid+1,k=left;
 78     while(i<=mid&&j<=right)
 79         arr[i]<=arr[j]?
 80             tmp[k++]=arr[i++]:
 81             tmp[k++]=arr[j++],sum+=mid-i+1;//Sum Is Used To Count The Reverse Alignment
 82     while(i<=mid)tmp[k++]=arr[i++];
 83     while(j<=right)tmp[k++]=arr[j++];
 84     R(i,left,right)arr[i]=tmp[i];
 85 }
 86 Iv Bucket_Sort(int a[],int left,int right){
 87     int mx=0;
 88     R(i,left,right)
 89         Cmax(mx,a[i]),++tot[a[i]];
 90     ++mx;
 91     while(mx--)
 92         while(tot[mx]--)
 93             a[right--]=mx;
 94 }
 95 */
 96 int n,m,a[N],sum_start,tmp[N];
 97 Iv Merge_Sort(int arr[],int left,int right,int &sum){
 98     if(left>=right)return;
 99     int mid=left+right>>1;
100     Merge_Sort(arr,left,mid,sum),Merge_Sort(arr,mid+1,right,sum);
101     int i=left,j=mid+1,k=left;
102     while(i<=mid&&j<=right)
103         arr[i]<=arr[j]?
104             tmp[k++]=arr[i++]:
105             (tmp[k++]=arr[j++],sum+=mid-i+1);//Sum Is Used To Count The Reverse Alignment
106     while(i<=mid)tmp[k++]=arr[i++];
107     while(j<=right)tmp[k++]=arr[j++];
108     R(i,left,right)arr[i]=tmp[i];
109 }
110 int main(){
111     int n;
112     while(scanf("%d %d",&n,&m)!=EOF,n,m){
113         sum_start=0;
114         int sum_end,num_cnt=0;
115         R(i,1,n)
116             R(j,1,m){
117                 int num=read();
118                 !num?
119                     sum_end=i:
120                     a[++num_cnt]=num;
121             }
122         Merge_Sort(a,1,num_cnt,sum_start);
123         D_e(sum_start);
124         sum_end=n-sum_end;
125         if(m&1)sum_end=0;
126         (sum_start&1)==(sum_end&1)?
127             printf("YES\n"):
128             printf("NO\n");
129     }
130     return 0;
131 }
132 /*
133     Note:
134         When Commas Are Used In Trinary Operators, Parentheses Shoule Be Used.
135     Error:
136         None.
137 */