首页 > 代码库 > BZOJ2464: 中山市选[2009]小明的游戏
BZOJ2464: 中山市选[2009]小明的游戏
2464: 中山市选[2009]小明的游戏
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 280 Solved: 124
[Submit][Status]
Description
小明最近喜欢玩一个游戏。给定一个n * m的棋盘，上面有两种格子#和@。游戏的规则很简单：给定一个起始位置和一个目标位置，小明每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是0，否则费用是1。请编程计算从起始位置移动到目标位置的最小花费。
Input
输入文件有多组数据。
输入第一行包含两个整数n，m，分别表示棋盘的行数和列数。
输入接下来的n行，每一行有m个格子（使用#或者@表示）。
输入接下来一行有四个整数x1, y1, x2, y2，分别为起始位置和目标位置。
当输入n，m均为0时，表示输入结束。
Output
对于每组数据，输出从起始位置到目标位置的最小花费。每一组数据独占一行。
Sample Input
2 2
@#
#@
0 0 1 1
2 2
@@
@#
0 1 1 0
0 0
@#
#@
0 0 1 1
2 2
@@
@#
0 1 1 0
0 0
Sample Output
2
0
0
HINT
对于100%的数据满足：1 < = n, m <= 500。
Source
题解：
对于这种题目我只能说呵呵。。。
裸最短路吧，连spfa都不卡。。。
代码：
View Code
对于这种题目我只能说呵呵。。。
裸最短路吧，连spfa都不卡。。。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 1000000+5 26 27 #define maxm 1000000 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 #define num(i,j) ((i-1)*m+j) 45 46 using namespace std; 47 48 inline int read() 49 50 { 51 52 int x=0,f=1;char ch=getchar(); 53 54 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 55 56 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 57 58 return x*f; 59 60 } 61 struct edge{int go,next,w;}e[2*maxn]; 62 63 int n,m,k,s,t,a[maxn],tot,d[maxn],head[maxn]; 64 65 bool v[maxn]; 66 queue<int>q; 67 char st[maxn]; 68 const int dx[4]={0,1,0,-1}; 69 const int dy[4]={1,0,-1,0}; 70 71 void insert(int x,int y,int z) 72 73 { 74 75 e[++tot].go=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot; 76 77 } 78 79 int spfa(int s,int t) 80 81 { 82 83 for(int i=1;i<=n*m;++i)d[i]=inf; 84 85 memset(v,0,sizeof(v)); 86 87 d[s]=0;q.push(s); 88 89 while(!q.empty()) 90 91 { 92 93 int x=q.front();q.pop();v[x]=0; 94 95 for(int i=head[x],y;i;i=e[i].next) 96 97 if(d[x]+e[i].w<d[y=e[i].go]) 98 99 {100 101 d[y]=d[x]+e[i].w;102 103 if(!v[y]){v[y]=1;q.push(y);}104 105 }106 107 }108 return d[t];109 110 }111 112 int main()113 114 {115 116 freopen("input.txt","r",stdin);117 118 freopen("output.txt","w",stdout);119 120 while(1)121 {122 n=read(),m=read();123 if(n*m==0)break;124 memset(head,0,sizeof(head));tot=0;125 for1(i,n)126 {127 scanf("%s",st+1);128 for1(j,m)a[num(i,j)]=st[j]==‘#‘?0:1;129 }130 for1(i,n)131 for1(j,m)132 for0(k,3)133 {134 int ii=i+dx[k],jj=j+dy[k];135 if(ii<1||ii>n||jj<1||jj>m)continue;136 insert(num(i,j),num(ii,jj),a[num(i,j)]!=a[num(ii,jj)]);137 }138 int x1=read()+1,y1=read()+1,x2=read()+1,y2=read()+1;139 printf("%d\n",spfa(num(x1,y1),num(x2,y2))); 140 }141 142 return 0;143 144 }
BZOJ2464: 中山市选[2009]小明的游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。