网站架构招聘,wordpress 链接新窗口打开,做照片的网站有哪些软件,网站建设 课题研究的背景文章目录 [Grid Ice Floor](https://atcoder.jp/contests/abc311/tasks/abc311_d)问题建模问题分析1.分析移动时前后两个点之间的联系2.方法1通过BFS将所有按照给定运动方式可以到达的点都标记代码 3.方法2采用DFS来标记路径上的点的运动状态代码 Grid Ice Floor 问题建模
给定… 文章目录 [Grid Ice Floor](https://atcoder.jp/contests/abc311/tasks/abc311_d)问题建模问题分析1.分析移动时前后两个点之间的联系2.方法1通过BFS将所有按照给定运动方式可以到达的点都标记代码 3.方法2采用DFS来标记路径上的点的运动状态代码 Grid Ice Floor 问题建模
给定一个n*m的字符矩阵有’.‘和’#‘两种字符其中’.为冰块是可移动的到的地方‘#为岩石无法移动到该地方。从点(2,2)出发出发时选择一个方向移动持续移动至撞上岩石时停止并重新选择移动方向。问由点(2,2)出发最多可以经过的冰块数量为多少。
问题分析
1.分析移动时前后两个点之间的联系
若前一个点是由停止后选择新的移动方向进行移动则后一个点为保持前一个点的移动方向进行移动。若前一个点是移动的则到后一个点既有可能保持与前一个点同样的移动方向继续移动也有可能是无法移动从而停止。通过分析两点间的联系可以发现每个点的状态有2大类一类为停止一类为运动运动里有按运动方向分为上下左右四种。
2.方法1通过BFS将所有按照给定运动方式可以到达的点都标记
因为任意一个点只要有一种运动状态被标记则该点一定可以由(2,2)点到达那我们可以让(2,2)为起点跑BFS将所有可以可到达路径上的点都标记最终统计所有被标记过的点即可得到答案。
代码
#includebits/stdc.h#define x first
#define y second
#define C(i) str[0][i]!str[1][i]
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pairint, int PII;
typedef pairLL, LL PLL;
const int N 210, Mod 998244353;
int n,m;
string g[N];
bool st[N][N][5];///记录该点的5种状态
int dx[4]{-1,0,1,0};
int dy[4]{0,1,0,-1};void bfs(){memset(st,false,sizeof(st));st[1][1][4]true;queueint q;///将坐标信息和状态映射为一个整数并出入队列中q.push(5*(m1)4);while(q.size()){int qtq.front();q.pop();int x(qt/5)/m;int y(qt/5)%m;int dqt%5;if(d4){///若当前状态为停止则选择新的方向移动for(int i0;i4;i){int nxxdx[i],nyydy[i];if(nx0nxn-1ny0nym-1g[nx][ny]!#!st[nx][ny][i]){st[nx][ny][i]true;q.push(5*(m*nxny)i);}}}else {int nxxdx[d],nyydy[d];///若当前运动方向可以接着移动则继续移动否则停止并选择新的方向if(nx0nxn-1ny0nym-1g[nx][ny]!#!st[nx][ny][d]){st[nx][ny][d]true;q.push(5*(m*nxny)d);}else {if(!st[x][y][4]){st[x][y][4]true;q.push(5*(m*xy)4);}}}}
}void solve() {cin n m;for(int i0;in;i) cin g[i];bfs();int cnt0;for(int i0;in;i){for(int j0;jm;j){///若该点有一种状态被标记则该点可达cnt(st[i][j][0]|st[i][j][1]|st[i][j][2]|st[i][j][3]|st[i][j][4]);}}cout cntendl;
} int main() {int t 1;//cin t;while (t--) solve();return 0;
}3.方法2采用DFS来标记路径上的点的运动状态
代码
停止后再选择新的移动方向可以不用设置为一个单独的状态而是直接选择新的方向从而省去停止状态
#includebits/stdc.h#define x first
#define y second
#define C(i) str[0][i]!str[1][i]
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pairint, int PII;
typedef pairLL, LL PLL;
const int N 210, Mod 998244353;
int n,m;
string g[N];
bool st[N][N][4];
int dx[4]{-1,0,1,0};
int dy[4]{0,1,0,-1};void dfs(int x,int y,int d){if(g[x][y]#||st[x][y][d]) return ;st[x][y][d]true;int nxxdx[d],nyydy[d];if(g[nx][ny]!#){///可以继续移动dfs(nx,ny,d);}else{//更换方向for(int i0;i4;i){nxxdx[i],nyydy[i];dfs(nx,ny,i);}}
}void solve() {cin n m;for(int i0;in;i) cin g[i];memset(st,false,sizeof(st));dfs(1,1,3);int cnt0;for(int i0;in;i){for(int j0;jm;j){cnt(st[i][j][0]|st[i][j][1]|st[i][j][2]|st[i][j][3]);}}cout cntendl;
} int main() {int t 1;//cin t;while (t--) solve();return 0;
}
