20161026 ADV

题目大意从矩阵1走到M的最短路径的数目,0为path, 9不可通过
只能沿x方向或者y方向行走,两个格子的距离为|x2-x1|+|y2-y1|


Code DFS

#include "stdafx.h"
#include <stdio.h>
int p[6][2];//row 0 will not be used
int a[8][8];//column 0, row 0 will not be used
int book[8][8];//column 0, row 0 will not be used
int num[5];//num[0] will not be used
int next[4][2]={{0,1},//右
                {1,0},//下
               {0,-1},//左
               {-1,0}};
int N,M;
int result[5];//column 0 will not be used
int stopx;
int stopy;
int min[5];

void dfs(int x,int y, int step, int l)
{
   int tx,ty,k;
   if(x==stopx && y==stopy){
      if(step<min[l]){
         result[l]=1;
         min[l]=step;
      }else if(step==min[l]){
         result[l] += 1;
      }
      return;
   }
   if(step>min[l])//剪枝.未到达但是步数已经超过目前的最小值
      return;
   for(k=0;k<=3;k++){
      tx=x+next[k][0];
      ty=y+next[k][1];
      if(tx<1 || tx>N || ty<1 || ty>N)
         continue;
      if(a[tx][ty]!=9 && book[tx][ty]==0){
         book[tx][ty]=1;
         dfs(tx,ty,step+1,l);
         book[tx][ty]=0;
      }
   }
}
int _tmain(int argc, _TCHAR* argv[])
{
   int T;
   int tc;
   int answer;
   int i,j;
   int l;
   int stx,sty;
   freopen("20161026i.txt","r",stdin);
   freopen("20161026o.txt","w",stdout);
   setbuf(stdout,NULL);
   scanf("%d",&T);
   for(tc=1;tc<=T;tc++){
      answer=1;//对于每个case初始化结果为1
      scanf("%d %d",&N,&M);//N方阵的行或者列，M最终到达的点
      for(i=1;i<=N;i++){
         for(j=1;j<=N;j++){
            scanf("%d", &a[i][j]);
            if(a[i][j]>0 && a[i][j]<=M){
               p[a[i][j]][0]=i;//记录经过的点
               p[a[i][j]][1]=j;
            }
         }
      }

      for(i=0;i<5;i++){
         result[i]=0;
         min[i]=99999999;
      }
      for(l=1;l<M;l++){
         for(i=0;i<=N;i++){
            for(j=0;j<=N;j++)
               book[i][j]=0;
         }
         stx=p[l][0];
         sty=p[l][1];
         stopx=p[l+1][0];
         stopy=p[l+1][1];
         book[stx][sty]=1;
         dfs(stx,sty,0,l);//起始点坐标, step数, 第L段
      }
      for(l=1;l<M;l++){
         answer = answer*result[l];
      }
      printf("#%d %d\n",tc,answer);
   }
   return 0;
}

Code DFS


Input
5
5 4 N为5, M为4
1 0 0 0 0
0 0 0 0 0
0 2 0 4 0
9 0 0 9 0
0 0 0 3 0
3 3
1 0 0
0 2 9
0 9 3
6 5
0 0 0 0 0 9
0 0 0 0 9 0
0 0 0 5 0 0
2 9 9 0 0 9
3 0 0 0 0 0
1 0 0 0 0 4
7 2
0 0 0 0 0 0 0
0 9 9 9 9 9 0
0 0 0 0 0 9 0
0 9 9 0 0 9 0
0 9 0 0 2 9 0
0 9 9 9 9 9 0
0 0 0 0 0 0 1
7 5
1 3 0 0 0 0 0
9 0 0 0 0 0 0
0 0 5 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 4
0 0 0 0 0 0 2

Output
#1 18
#2 0
#3 42
#4 3
#5 156508320