CF Zepto Code Rush 2014 B. Om Nom and Spiders
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Om Nom really likes candies and doesn't like spiders as they frequently steal candies. One day Om Nom fancied a walk in a park. Unfortunately, the park has some spiders and Om Nom doesn't want to see them at all.
The park can be represented as a rectangular n × m field. The park has k spiders, each spider at time 0 is at some cell of the field. The spiders move all the time, and each spider always moves in one of the four directions (left, right, down, up). In a unit of time, a spider crawls from his cell to the side-adjacent cell in the corresponding direction. If there is no cell in the given direction, then the spider leaves the park. The spiders do not interfere with each other as they move. Specifically, one cell can have multiple spiders at the same time.
Om Nom isn't yet sure where to start his walk from but he definitely wants:
We know that Om Nom moves by jumping. One jump takes one time unit and transports the little monster from his cell to either a side-adjacent cell on the lower row or outside the park boundaries.
Each time Om Nom lands in a cell he sees all the spiders that have come to that cell at this moment of time. Om Nom wants to choose the optimal cell to start the walk from. That's why he wonders: for each possible starting cell, how many spiders will he see during the walk if he starts from this cell? Help him and calculate the required value for each possible starting cell.
Input
The first line contains three integers n, m, k (2 ≤ n, m ≤ 2000; 0 ≤ k ≤ m(n - 1)).
Each of the next n lines contains m characters — the description of the park. The characters in the i-th line describe the i-th row of the park field. If the character in the line equals ".", that means that the corresponding cell of the field is empty; otherwise, the character in the line will equal one of the four characters: "L"(meaning that this cell has a spider at time 0, moving left), "R"(a spider moving right), "U"(a spider moving up), "D"(a spider moving down).
It is guaranteed that the first row doesn't contain any spiders. It is guaranteed that the description of the field contains no extra characters. It is guaranteed that at time 0 the field contains exactly k spiders.
Output
Print m integers: the j-th integer must show the number of spiders Om Nom will see if he starts his walk from the j-th cell of the first row. The cells in any row of the field are numbered from left to right.
Sample test(s)
Input
3 3 4
...
R.L
R.U
Output
0 2 2
Input
2 2 2
..
RL
Output
1 1
Input
2 2 2
..
LR
Output
0 0
Input
3 4 8
....
RRLL
UUUU
Output
1 3 3 1
Input
2 2 2
..
UU
Output
0 0
Note
Consider the first sample. The notes below show how the spider arrangement changes on the field over time:
... ... ..U ...
R.L -> .*U -> L.R -> ...
R.U .R. ..R ...
Character "*"represents a cell that contains two spiders at the same time.
물문제는 간사하게 두 번째로 놓았다.
AC 코드는 다음과 같습니다.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define M 100005
#define ll long long
using namespace std;
char a[2005][2005];
int main()
{
int n,m,k;
int i,j;
int b[2005];
memset(b,0,sizeof b);
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<n;i++)
scanf("%s",a[i]);
for(i=1;i<n;i++)
for(j=0;j<m;j++)
{
if(a[i][j]=='R'&&i+j<m)// i+j<m , WA,
b[i+j]++;
if(a[i][j]=='L'&&j-i>=0)
b[j-i]++;
if(a[i][j]=='U')
{
if(i%2==0)
b[j]++;
}
}
for(i=0;i<m;i++)
printf("%d ",b[i]);
printf("
");
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.