[aha0410]水管工

// aha0410.cpp : 水管工
#include "stdafx.h"
#include <stdio.h>
int a[50][50];
int mark[50][50],n,m,flag=0;
typedef struct _note{
   int x;
   int y;
}note;
note s[100];
int top=-1;
void plumber(int x,int y,int front)
{
   int i;
   if(x==n-1 && y==m){
      flag=1;
      for(i=0;i<=top;i++)
         printf("(%d,%d)\n",s[i].x,s[i].y);
      return;
   }
   if(x<0 || x>n-1 || y<0 || y>m-1)
      return;
   if(mark[x][y]==1)
      return;
   mark[x][y]=1;

   top++,s[top].x=x,s[top].y=y;

   if(a[x][y]>=5 && a[x][y]<=6)
   {
      if(front==1)
         plumber(x,y+1,1);
      if(front==2)
         plumber(x+1,y,2);
      if(front==3)
         plumber(x,y-1,3);
      if(front==4)
         plumber(x-1,y,4);
   }

   if(a[x][y]>=1 && a[x][y]<=4)
   {
      if(front==1){
         plumber(x+1,y,2);
         plumber(x-1,y,4);
      }
      if(front==2){
         plumber(x,y+1,1);
         plumber(x,y-1,3);
      }
      if(front==3){
         plumber(x+1,y,2);
         plumber(x-1,y,4);
      }
      if(front==4){
         plumber(x,y+1,1);
         plumber(x,y-1,3);
      }
   }
   mark[x][y]=0;//回溯
   top--;
   return;
}

int _tmain(int argc, _TCHAR* argv[])
{
   int i,j,num=0;
   freopen("aha0410in.txt","r",stdin);
   scanf("%d %d",&n,&m);
   for(i=0;i<n;i++)
      for(j=0;j<m;j++)
         scanf("%d",&a[i][j]);
   plumber(0,0,1);
   if(flag==0)
      printf("Impossible......\n");
   return 0;
}

/* input
5 4
5 3 5 3
1 5 3 0
2 3 5 1
6 1 1 5
1 5 5 4
*/

/* output
(0,0)
(0,1)
(1,1)
(2,1)
(2,2)
(2,3)
(3,3)
(4,3)
*/