首頁新隨筆新文章聯(lián)系聚合

posts - 16,comments - 33,trackbacks - 0

2007年8月

>

日

一

二

三

四

五

六

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

常用鏈接

留言簿(2)

隨筆分類

隨筆檔案

blog

yoyo在百度的小屋

C++ study

C++ preference

OJ

JOJ
POJ

STL學(xué)習(xí)

center of STL study
STL中文站

yoyo's link

youtube

搜索

閱讀排行榜

評論排行榜

JOJ 1034 Worm Turns

WA了一次，最后發(fā)現(xiàn)竟然是多次計(jì)算時(shí)沒給result賦初值，改了以后就AC了~

題目是寫一個(gè)超簡化版的貪吃蛇，在50*50的矩陣中，起始位置是蛇頭位于的（25，30），蛇尾在（25，11），蛇占20個(gè)格。蛇可以向E W N S四個(gè)方向移動(dòng)，當(dāng)然不能反向移動(dòng)，也不能撞倒自己或者撞倒墻.

輸入多組case，每組是一串字符，表示每次的移動(dòng)方向.
輸出是否能完成這些移動(dòng)，如果不能，就判斷是在第幾次移動(dòng)時(shí)撞倒自己還是墻.

我的思路是在矩陣中，將蛇占據(jù)的位置用1標(biāo)記，將蛇頭到蛇尾的20個(gè)坐標(biāo)存入一個(gè)vector，然后每次移動(dòng)，先判斷是否撞倒墻，如果沒撞倒墻，就先將蛇尾刪除，將舊蛇頭的位置置0（新蛇頭可以是舊蛇尾），再將新的蛇頭存入vector，判斷新的蛇頭所在的位置是否為0，若為被占據(jù)，則置1，繼續(xù)移動(dòng).

覺得自己寫得很冗余，開始時(shí)只記錄了蛇頭和蛇尾的坐標(biāo)，以為根據(jù)蛇頭移動(dòng)就可以判斷蛇尾的移動(dòng)，寫著寫著就發(fā)現(xiàn)問題了，臨時(shí)加了個(gè)vector來存蛇的坐標(biāo)，所以程序有點(diǎn)亂，也只有這樣了，以后再改改吧~

我的AC代碼：

1

#include<iostream>
2

#include<vector>
3

#include<string>
4

using namespace std;
5

struct point
6

{
7

int row;
8

int col;
9

};
10

int main()
11

{
12

int i,j,n,index,result=1;
13

string moves;
14

char move;
15

point p;
16

vector<point>v;
17

while(1)
18

{
19

result=1;
20

cin>>n;
21

if(n==0)break;
22

23

int s[50][50]={0};
24

int fristr=24,fristc=29,lastr=24,lastc=10;
25

cin>>moves;
26

for(j=10;j<30;j++)
27

{
28

s[24][j]=1;
29

p.row=24;
30

p.col=j;
31

v.push_back(p);
32

}
33

for(index=0;index<n;index++)
34

{
35

move=moves[index];
36

if(move=='E')++fristc;
37

if(move=='W')--fristc;
38

if(move=='N')--fristr;
39

if(move=='S')++fristr;
40

if(fristr*(fristr-49)>0||fristc*(fristc-49)>0)
41

{
42

cout<<"The worm ran off the board on move "<<index+1<<"."<<endl;
43

result=0;
44

break;
45

}
46

v.erase(v.begin());
47

p.row=fristr;
48

p.col=fristc;
49

v.push_back(p);
50

s[lastr][lastc]=0;
51

lastr=v[0].row;
52

lastc=v[0].col;
53

if(s[fristr][fristc])
54

{
55

cout<<"The worm ran into itself on move "<<index+1<<"."<<endl;
56

result=0;
57

break;
58

}
59

s[fristr][fristc]=1;
60

}
61

if(result)printf("The worm successfully made all %d moves.\n", n);
62

v.clear();
63

getchar()
64

}
65

}
66

posted on 2007-08-17 08:48 yoyouhappy 閱讀(963) 評論(4) 編輯收藏引用所屬分類: yoyo的解題報(bào)告、acm/icpc

FeedBack:

# re: JOJ 1034 Worm Turns

2007-08-17 14:01 | tb

蛇頭如果與身體相撞必然會形成一個(gè)矩形。可以根據(jù)輸入的字符串判斷出來。
但是在開始的時(shí)候（前20步）是個(gè)需要特別處理的情況回復(fù) 更多評論

# re: JOJ 1034 Worm Turns

2007-08-17 14:06 | tb

再想了一下不一定是矩形但是在東西和南北方向上的位肯定是0 回復(fù) 更多評論

# re: JOJ 1034 Worm Turns

2007-08-17 14:09 | tb

可以把輸入分為兩部分一個(gè)只有南北一個(gè)只有東西（保持順序）然后看位移是不是0
回復(fù) 更多評論

# re: JOJ 1034 Worm Turns

2007-08-18 10:36 | yoyouhappy

@tb
不太明白你的意思。。。。
位移為什么會是0呢，誰的位移為0？我有點(diǎn)糊涂了回復(fù) 更多評論

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。


相關(guān)文章: POJ 1088 滑雪 POJ 1018 Communication System 暫時(shí)搬家 JOJ 1101 DNA Sorting 詭異阿~ JOJ 1034 Worm Turns POJ 1002 487-3279 yoyo的假期作業(yè)

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

常用鏈接

留言簿(2)

隨筆分類

隨筆檔案

blog

C++ study

OJ

STL學(xué)習(xí)

yoyo's link

搜索

最新評論

閱讀排行榜

評論排行榜