首页 > 代码库 > 地道战
地道战
地道战
Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 959 Solved: 615
Description
大家一定看过地道战的电视吧。话说小兵张嘎有一回也跑去支援地道战了。那是河北的一个小镇里，这个小镇比较复杂，什么样的人都有。所以张嘎不能走大街，只能在地道里走。但根据地质情况不同，所以同样长的街道，地道里要走的时间可能不一样。当然每条街道下面都有地道，而且在街道连接处地道也有连接。有一天张嘎在A处，突然发现有大部队的敌军前来，所以他必须以尽快的速度跑到B处通知分队隐蔽，每条地道上都标出了他要走的时间。请帮他算一下，怎么走时间最短。
A +---2---+---3---+----1---+----2---+ | | | | | 2 1 2 2 3 | | | | | +---2---+---3---+----4---+---5----+ | | | | | 3 4 1 2 3 | | | | | +---2---+---2---+---1----+---4----+ | | | | | 2 2 1 3 4 | | | | | +---1---+---3---+---2----+---3----+ B
Input
有多个测试案例。每个测试案例，第1行输入2个整数N和M (1 <= n,m <=100)分别表示横向的街道的条数和纵向街道的条数。以下n行每行输入各段地道（横向）需要的时间，每行按从左到右的顺序一下m行每行输入各段地道（纵向）需要的时间，每列按从上到下的顺序处理到文件末尾
Output
对每个测试案例输出一行，输出他从A到B的最短时间
Sample Input
4 52 3 1 22 3 4 52 2 1 41 3 2 32 3 21 4 22 1 12 2 33 3 4
Sample Output
13
1 #include<stdio.h> 2 #define INF 1<<30 3 int min(int a,int b) 4 { 5 return a<=b?a:b; 6 } 7 8 int main() 9 {10 freopen("a.txt","r",stdin);11 int m,n;12 int cross[200][200],vertical[200][200];13 int i,j,k;14 int dp[250][250];15 while(scanf("%d%d",&m,&n)==2)16 {17 for(i=0;i<=m;i++)18 for(j=0;j<=n;j++)19 {20 cross[i][j]=INF;21 vertical[i][j]=INF;22 }23 for(i=1;i<=m;i++)24 for(j=1;j<=n-1;j++)25 {26 scanf("%d",&cross[i][j]);27 }28 for(i=1;i<=m-1;i++)29 for(j=1;j<=n;j++)30 {31 scanf("%d",&vertical[i][j]);32 }33 for(i=0;i<=m;i++)34 for(j=0;j<=n;j++)35 {36 dp[i][j]=INF;37 }38 39 dp[1][1]=0;40 for(i=1;i<=m;i++)41 for(j=1;j<=n;j++)42 {43 if(i==1&&j==1)44 continue;45 dp[i][j]=0;46 dp[i][j]+=min(dp[i-1][j],dp[i][j-1])+min(cross[i][j-1],vertical[j][i-1]);47 }48 for(i=1;i<=m;i++)49 {50 printf("\n");51 for(j=1;j<=n;j++)52 {53 printf("%-4d",dp[i][j]);54 }55 }56 printf("%d\n",dp[m][n]);57 }58 return 0;59 }60
地道战
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。