POJ 2983 M × N Puzzle

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 */

view code