Submission #00133


ソースコード

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
typedef struct{
int y,x;
}P;
typedef struct{
int d[1000][1000];
}M;
typedef struct{
int cy[9];
int cx[9];
}cheese;
M m;
cheese c;
int main(){
char maps[1000][1000];
int sy,sx;
int gy,gx;
int h,w;
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int n;
int ans=-1;
scanf("%d %d %d",&h,&w,&n);
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
m.d[i][j]=-1;
cin>>maps[i][j];
if(maps[i][j]=='S'){
sy=i;
sx=j;
m.d[i][j]=0;
}else if(maps[i][j]>='1'&&maps[i][j]<='9'){
int num=maps[i][j]-'1';
c.cy[num]=i;
c.cx[num]=j;
}
}
}
M temp=m;
for(int i=0;i<n;i++){
gy=c.cy[i];
gx=c.cx[i];
queue<P>que;
que.push((P){sy,sx});
while(!que.empty()){
P p=que.front();
que.pop();
int y=p.y;
int x=p.x;
if(y==gy&&x==gx)break;
for(int j=0;j<4;j++){
int ny=y+dy[j];
int nx=x+dx[j];
if(ny>=0&&ny<h&&nx>=0&&nx<w&&maps[ny][nx]!='X'&&m.d[ny][nx]==-1){
m.d[ny][nx]=m.d[y][x]+1;
que.push((P){ny,nx});
}
}
}
sy=gy;
sx=gx;
ans+=m.d[gy][gx]+1;
m=temp;
}
cout<<ans<<endl;
return 0;
}

ステータス

項目 データ
問題 0005 - チーズ(Cheese)
ユーザー名 ei1630
投稿日時 2016-11-09 18:54:14
言語 C++11
状態 Wrong Answer
得点 80
ソースコード長 1228 Byte
最大実行時間 88 ms
最大メモリ使用量 9296 KB

セット

セット 得点 Cases
1 in1 20 / 20 in1.txt
2 in2 20 / 20 in2.txt
3 in3 20 / 20 in3.txt
4 in4 20 / 20 in4.txt
5 in5 0 / 20 in5.txt

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 31 ms 8288 KB
1
in2.txt AC 21 ms 8264 KB
2
in3.txt AC 26 ms 8348 KB
3
in4.txt AC 88 ms 9276 KB
4
in5.txt WA 78 ms 9296 KB
5