Submission #00043


ソースコード

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
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define F first
#define S second
#define LLINF (1LL<<60)
#define INF (1<<29)
using namespace std;
typedef pair<long long,long long> P;
//今いる行の東から南までを反転して下に行く
//もし今いる場所より右から南がなくなるか下の行についたら終わり
//幅でその場所に何回来るかを先に求める
//それを元に最終的な東南を求める
//最後に一回シミュレーションする
long long maps[1005][1005]={0};
bool flag[1005][1005];
long long cnts[1005][1005]={0};
main(){
long long H,W,N;
memset(flag,1,sizeof(flag));
cin>>H>>W>>N;
for(int i=1;i<=H;i++){
for(int j=1;j<=W;j++){
cin>>maps[i][j];
flag[i][j]=false;
}
}
long long nowh,noww;
cnts[1][1]=N-1;
queue<P> que;
que.push(P(1,2));
que.push(P(2,1));
while(!que.empty()){
nowh=que.front().F;
noww=que.front().S;
if(nowh<=H&&noww<=W){
// cout<<nowh<<" "<<noww<<endl;
if(maps[nowh-1][noww]==0&&nowh-1>=1){
cnts[nowh][noww]+=cnts[nowh-1][noww]%2;
}
if(maps[nowh][noww-1]==1&&noww-1>=1){
cnts[nowh][noww]+=cnts[nowh][noww-1]%2;
}
cnts[nowh][noww]+=cnts[nowh-1][noww]/2;
cnts[nowh][noww]+=cnts[nowh][noww-1]/2;
flag[nowh][noww]=true;
if(flag[nowh-1][noww+1]==true){
que.push(P(nowh,noww+1));
}
if(flag[nowh+1][noww-1]==true){
que.push(P(nowh+1,noww));
}
}
que.pop();
}
/*
for(int i=0;i<=H;i++){
for(int j=0;j<=W;j++){
cout<<cnts[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
*/
for(int i=1;i<=H;i++){
for(int j=1;j<=W;j++){
maps[i][j]=(cnts[i][j]+maps[i][j])%2;
//cout<<maps[i][j]<<" ";
}
//cout<<endl;
}
nowh=noww=1;
while(nowh<=H&&noww<=W){
if(maps[nowh][noww]==0){
nowh++;
}
else{
noww++;
}
}
cout<<nowh<<" "<<noww<<endl;
}

ステータス

項目 データ
問題 0004 - 散歩 (Walk)
ユーザー名 ei1417
投稿日時 2016-02-08 18:27:26
言語 C++11
状態 Accepted
得点 100
ソースコード長 1972 Byte
最大実行時間 147 ms
最大メモリ使用量 17288 KB

セット

セット 得点 Cases
1 Subtask1 10 / 10 *in1
2 Subtask2 10 / 10 *in2
3 Subtask3 10 / 10 *in3
4 Subtask4 10 / 10 *in4
5 Subtask5 10 / 10 *in5
6 Subtask6 10 / 10 *in6
7 Subtask7 10 / 10 *in7
8 Subtask8 10 / 10 *in8
9 Subtask9 10 / 10 *in9
10 Subtask10 10 / 10 *in10

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
2009-ho-t4-in1 AC 18 ms 4572 KB
1
2009-ho-t4-in2 AC 15 ms 4776 KB
2
2009-ho-t4-in3 AC 16 ms 5020 KB
3
2009-ho-t4-in4 AC 27 ms 5284 KB
4
2009-ho-t4-in5 AC 29 ms 8312 KB
5
2009-ho-t4-in6 AC 18 ms 7736 KB
6
2009-ho-t4-in7 AC 46 ms 12724 KB
7
2009-ho-t4-in8 AC 47 ms 12832 KB
8
2009-ho-t4-in9 AC 139 ms 17288 KB
9
2009-ho-t4-in10 AC 147 ms 17204 KB
10