C. Robot(BFS)
C. Robot
There is a rectangular field in the lab of Institution of Advanced Robotic Technology.
Many robots are about to release to this field one after another. They always enter the field from the upper left cell and leave from the lower right cell. In between, they can move vertically or horizontally to an adjacent cell on each step. At any time, there is at most one robot on the field.
Robots can be divided into two types: Type A and Type B. During the movement, a robot will write down its type mark (A or B) in each cell on its track, which will cover all previous marks in the same cell. Notice that there is no mark on the field at the beginning.
Here is an example: initially there is no mark on the field (Figure 1); first, a robot of type A crosses the field from top-left to bottom right (Figure 2). After that, a robot of type B crosses and its tracks are partially covering the A’s (Figure 3).
..... AAAA. BBAA.
..... ..AA. .BBBB
..... ...A. ...AB
..... .AAA. .ABBB
..... ..AAA ..BBB
(1) (2) (3)
You are given the marks on the field after all robots have crossed. Write a program to determine the minimal possible number of released robots.
Input
For each test case:
The first line contains two integers h and w, indicates the height and width of the field. 1 ≤ h, w ≤ 4 000.
Then follows h lines, each line contains w characters: each character indicates the mark in the corresponding cell. A dot (“.”) indicates that there is no mark on this cell.
There is at least one mark on the field.
Output
Sample Input
2 3 3 AA. .A. .AA 5 8 AAB..... .ABBB... .AAAAA.. ..BBBAAB .....AAA
Sample Output
1 2
#include<stdio.h> #include<queue> #include<iostream> using namespace std; typedef struct nnn { int x,y; }node; int vist[4005][4005]; char map[4005][4005]; int n,m,k,dir[4][2]={0,1,0,-1,1,0,-1,0},tf; void init() { for(int i=0;i<n;i++) for(int j=0;j<m;j++) vist[i][j]=0; } queue<node>q[2]; void bfs(int flag) { node p,s; k++; while(!q[flag].empty()) { s=q[flag].front(); q[flag].pop(); if(s.x==0&&s.y==0)tf=1; for(int e=0;e<4;e++) { p.x=s.x+dir[e][0]; p.y=s.y+dir[e][1]; if(p.x>=0&&p.x<n&&p.y>=0&&p.y<m&&vist[p.x][p.y]==0&&map[p.x][p.y]!='.') { vist[p.x][p.y]=1; if(map[p.x][p.y]!=map[s.x][s.y]) q[!flag].push(p); else q[flag].push(p); } } } } int main() { int t,f,flag; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0;i<n;i++)scanf("%s",map[i]); k=0; tf=0; while(!q[0].empty())q[0].pop(); while(!q[1].empty())q[1].pop(); if(map[0][0]!=map[n-1][m-1])f=1;else f=0; if(map[n-1][m-1]!='.') { node s; init(); s.x=n-1; s.y=m-1; flag=0; vist[n-1][m-1]=1; q[0].push(s); while(!q[flag].empty()) { bfs(flag); flag=(!flag); } } else f=0; if(tf==0&&f)f=0; printf("%d\n",k-f); } }
相关文章
- 2017蓝桥杯省赛:青蛙跳杯子(BFS求最短路径长度)
- 好的,BFS,又学废了!
- L3-023 计算图(链式求导+bfs拓扑|dfs)「建议收藏」
- [蓝桥杯][历届试题]九宫重排(BFS+哈希)
- 九宫格拼图问题(BFS)
- 算法学习–分酒问题(BFS)[通俗易懂]
- 有了BFS,困难的谜题也不过如此,一个模板就够了
- P1443 马的遍历【BFS】
- J - Welcome Party ZOJ - 4109 【 并查集 + 优先队列 + BFS 】
- E - What a Ridiculous Election UVALive - 7672 【 BFS ,预处理各种状态 】
- 详解BFS,Dijkstra算法,Floyd算法是如何解决最短路径问题的
- 搜索算法dfs和bfs解析(附有例题)
- BFS(广度搜索|宽度搜索)无向图遍历(JAVA手把手深入解析)
- L3-008 喊山 (30 分) 【 BFS 】
- 7-13 肿瘤诊断 (30 分)【 BFS 】
- Fire Game (FZU 2150)(BFS)
- Catch That Cow (POJ - 3278)(简单BFS)
- Dungeon Master (POJ - 2251)【 三维 BFS 】
- Prime Path (POJ - 3126 )(BFS)
- Oil Deposits (HDU - 1241 )(DFS思路 或者 BFS思路)
- 数据结构实验之图论五:从起始点到目标点的最短步数(BFS)
- Ancient Go ( HDU - 5546 ) ( BFS 搜索是否相连)
- C. Connect 【 BFS + 暴力 】
- BFS广度优先搜索解决迷宫问题
- BFS算法模板与练习
- 深入探讨POJ2312BattleCity优先队列+BFS