codeforces 1064D. Labyrinth(제한된 BFS)
21016 단어 codeforces
D. Labyrinth time limit per test2 seconds memory limit per test512 megabytes inputstandard input outputstandard output You are playing some computer game. One of its levels puts you in a maze consisting of n lines, each of which contains m cells. Each cell either is free or is occupied by an obstacle. The starting cell is in the row r and column c. In one step you can move one square up, left, down or right, if the target cell is not occupied by an obstacle. You can’t move beyond the boundaries of the labyrinth.
Unfortunately, your keyboard is about to break, so you can move left no more than x times and move right no more than y times. There are no restrictions on the number of moves up and down since the keys used to move up and down are in perfect condition.
Now you would like to determine for each cell whether there exists a sequence of moves that will put you from the starting cell to this particular one. How many cells of the board have this property?
Input The first line contains two integers n, m (1 ≤ n, m ≤ 2000) — the number of rows and the number columns in the labyrinth respectively.
The second line contains two integers r, c (1 ≤ r ≤ n, 1 ≤ c ≤ m) — index of the row and index of the column that define the starting cell.
The third line contains two integers x, y (0 ≤ x, y ≤ 109) — the maximum allowed number of movements to the left and to the right respectively.
The next n lines describe the labyrinth. Each of them has length of m and consists only of symbols ‘.’ and ‘’. The j-th character of the i-th line corresponds to the cell of labyrinth at row i and column j. Symbol ‘.’ denotes the free cell, while symbol '’ denotes the cell with an obstacle.
It is guaranteed, that the starting cell contains no obstacles.
Output Print exactly one integer — the number of cells in the labyrinth, which are reachable from starting cell, including the starting cell itself.
Examples inputCopy 4 5 3 2 1 2 … .*. … … outputCopy 10 inputCopy 4 4 2 2 0 1 … …. … … outputCopy 7 Note Cells, reachable in the corresponding example, are marked with ‘+’.
First example:
+++… +*.+++ *+++. Second example:
.++. .+*. .++. .++.
제목: N*M의 지도를 하나 드리겠습니다.'*'는 갈 수 없는 지역을 표시합니다. 기점은 r, c입니다. 왼쪽으로 최대 x회, 오른쪽으로 최대 y회 이동합니다. 도착할 수 있는 장소가 얼마나 되는지 물어보세요.
사고방식: bfs의 방법이 뚜렷하다. 처음에 나는 바로 bfs를 한 번 사용했다.그러나 이것은 분명히 문제가 있다. 좌우 이동 횟수에 제한이 있기 때문에 반드시 어느 지점에 먼저 도착하는 것이 가장 좋은 것은 아니다. 그래서 우리는 어느 지점에 도착할 때 왼쪽과 오른쪽으로 이동하는 횟수를 표시하고 더 좋은 선택이 있으면 바꾼다.
코드는 다음과 같습니다.
#include
using namespace std;
const int MAX = 2020;
char str[MAX][MAX];
const int xx[4] = {0,1,0,-1};
const int yy[4] = {1,0,-1,0};
class Node{
public:
int l,r;
int x,y;
};
class Tag{
public:
int left,right;
Tag(){
left = right = -1;
}
};
Tag book[MAX][MAX];
int N,M;
int r,c;
int px,py;
void bfs(){
queue<Node> que;
Node e;
e.x = r;e.y = c;
e.l = 0;e.r = 0;
que.push(e);
book[r][c].left = book[r][c].right = 0;
while(!que.empty()){
Node v = que.front();que.pop();
for(int i=0;i<4;++i){
int nx = v.x + xx[i];
int ny = v.y + yy[i];
if(nx < 1 || ny < 1 || nx > N || ny > M)
continue;
if(str[nx][ny] == '*') continue;
Node es;
es.x = nx;es.y = ny;
es.l = v.l;es.r = v.r;
if(i == 2) es.l++;
if(i == 0) es.r++;
if(es.l <= px && es.r <= py){
if(es.l == book[nx][ny].left && es.r == book[nx][ny].right) continue;
// , 。
if(book[nx][ny].left == -1 || (es.l <= book[nx][ny].left && es.r <= book[nx][ny].right)){
que.push(es);
book[nx][ny].left = es.l;
book[nx][ny].right = es.r;
}
}
}
}
}
int main(void){
scanf("%d%d",&N,&M);
scanf("%d%d",&r,&c);
scanf("%d%d",&px,&py);
for(int i=1;i<=N;++i)
scanf("%s",str[i]+1);
bfs();
int res = 0;
for(int i=1;i<=N;++i){
for(int j=1;j<=M;++j){
if(book[i][j].left != -1)
res++;
}
}
printf("%d
",res);
return 0;
}
/*
Special data
10 10
10 4
10 9
...*******
.*.*******
.*.*******
.*.*******
.*.*******
.*.*......
.*.*.*****
.*........
.********.
..........
res = 43;
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.