bzoj2464 小明的游戏

Description

小明最近喜欢玩一个游戏。给定一个n * m的棋盘,上面有两种格子#和@。游戏的规则很简单:给定一个起始位置和一个目标位置,小明每一步能向上,下,左,右四个方向移动一格。如果移动到同一类型的格子,则费用是0,否则费用是1。请编程计算从起始位置移动到目标位置的最小花费。

Input

输入文件有多组数据。

输入第一行包含两个整数n,m,分别表示棋盘的行数和列数。

输入接下来的n行,每一行有m个格子(使用#或者@表示)。

输入接下来一行有四个整数x1, y1, x2, y2,分别为起始位置和目标位置。

当输入n,m均为0时,表示输入结束。

Output

对于每组数据,输出从起始位置到目标位置的最小花费。每一组数据独占一行。

spfa求最短路

#include<cstdio>
#include<queue>
int n,m,x1,y1,x2,y2;
char s[505][505];
int l[505][505];
bool in[505][505];
struct pos{
    int x,y;
};
std::queue<pos>q;
int xs[]={-1,0,1,0};
int ys[]={0,-1,0,1};
int main(){
    while(1){
        scanf("%d%d",&n,&m);
        if(n+m==0)break;
        for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                l[i][j]=2147483647;
            }
        }
        l[++x1][++y1]=0;
        q.push((pos){x1,y1});
        while(!q.empty()){
            pos w=q.front();q.pop();
            int x=w.x,y=w.y;
            in[x][y]=0;
            for(int i=0;i<4;i++){
                int xx=x+xs[i],yy=y+ys[i];
                if(!s[xx][yy])continue;
                if(s[xx][yy]!=s[x][y]){
                    if(l[x][y]+1<l[xx][yy]){
                        l[xx][yy]=l[x][y]+1;
                        if(!in[xx][yy])q.push((pos){xx,yy}),in[xx][yy]=1;
                    }
                }else{
                    if(l[x][y]<l[xx][yy]){
                        l[xx][yy]=l[x][y];
                        if(!in[xx][yy])q.push((pos){xx,yy}),in[xx][yy]=1;
                    }
                }
            }
        }
        printf("%d\n",l[x2+1][y2+1]);
    }
    return 0;
}
时间: 02-25

bzoj2464 小明的游戏的相关文章

针对明棋类游戏的策梅洛定理的每个人都能读懂的证明过程(下象棋、围棋、国际象棋等的必胜下法求解)

网上流传的博弈论策梅洛定理的中文证明资料,其证明都不是那么容易理解读懂.因此这里描述一下我的通俗一点的证明. 策梅洛定理:在有限步数内一定会结束的已经明确规则的明棋类游戏中(例如中国象棋.国际象棋),对于特定的任一局面,设A先下,B后下,那么要么A有必胜下法,要么B有必胜下法,要么A.B都有必和下法. 证明用的是归纳法. 把相邻的A走一步棋.B走一步棋的下法组合作为本证明中的一回合走法.证明对于有限n回合的棋类游戏局面(正规开局也算是一种局面),要么A有必胜下法(1),要么B有必胜下法(2),要

小明系列问题――小明序列(LIS)

小明系列问题――小明序列 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Practice HDU 4521 Description 大家都知道小明最喜欢研究跟序列有关的问题了,可是也就因为这样,小明几乎已经玩遍各种序列问题了.可怜的小明苦苦地在各大网站上寻找着新的序列问题,可是找来找去都是自己早已研究过的序列.小明想既然找不到,那就自己来发明一个新的序列问题吧!

hdu4521 小明系列问题——小明序列(LIS变种 (线段树+单点更新解法))

链接: huangjing 题目:中文题目 思路: 这个题目如果去掉那个距离大于d的条件,那么必然是一个普通的LIS,但是加上那个条件后就变得复杂了.用dp的解法没有看懂,我用的线段树的解法...就是采用延迟更新的做法,用为距离要大于d啊,所以我们在循环到第i的时候,就对(i-d-1)这个点进行更新,因为如果在(i-d-1)这个点更新了,会对后面的造成影响,然后线段树的tree[]数组存的是以i结尾的最长lis,那么每次询问的时候就找最大的tree[]就可以了... 代码: 小明系列问题--小明

NYOJ 49 开心的小明

开心的小明 时间限制:1000 ms  |  内存限制:65535 KB 难度:4 描述 小明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间.更让他高兴的是,妈妈昨天对他说:"你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N 元钱就行".今天一早小明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的N 元.于是,他把每件物品规定了一个重要度,分为5 等:用整数1~5 表示,第5 等最重要.他还从因特网上查到了每件物品的价格(都是整数元).

hunnu 11545小明的烦恼——找路径 (最大流)

小明的烦恼--找路径  Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:32768KB Total submit users: 45, Accepted users: 37 Problem 11545 : No special judgement Problem description   小明真的是个很厉害的人,每当老师有什么事时,总是会找到小明,二小明也总能解决,所以老师决定给小明一个奖励,给他额外的假期.小明当然很高兴

HDU 小明系列故事——师兄帮帮忙 快速幂

小明系列故事--师兄帮帮忙 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 4850    Accepted Submission(s): 1275 Problem Description 小明自从告别了ACM/ICPC之后,就开始潜心研究数学问题了,一则可以为接下来的考研做准备,再者可以借此机会帮助一些同学,尤其是漂亮的师妹.这不,班

NYOJ 懒省事的小明

懒省事的小明 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述       小明很想吃果子,正好果园果子熟了.在果园里,小明已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆.小明决定把所有的果子合成一堆. 因为小明比较懒,为了省力气,小明开始想点子了: 每一次合并,小明可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和.可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了.小明在合并果子时总共消耗的体力等于每次合并所耗体力之和. 因为还要花大力

NYOJ 55 懒省事的小明 (优先队列)

题目意思: http://acm.nyist.net/JudgeOnline/problem.php?pid=55 每一次合并,小明可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和.可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了.小明在合并果子时总共消耗的体力等于每次合并所耗体力之和. 因为还要花大力气把这些果子搬回家,所以小明在合并果子时要尽可能地节省体力.假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使小明耗费的体力最少,并

nyoj469 擅长排列的小明 II

擅长排列的小明 II 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述 小明十分聪明,而且十分擅长排列计算. 有一天小明心血来潮想考考你,他给了你一个正整数n,序列1,2,3,4,5......n满足以下情况的排列: 1.第一个数必须是1 2.相邻两个数之差不大于2 你的任务是给出排列的种数. 输入 多组数据.每组数据中输入一个正整数n(n<=55). 输出 输出种数. 样例输入 4 样例输出 4 思路: 由于A1一直是1,所以A2只能是2或3. 1.当A2=2时,从