Grid Ice Floor

问题建模

给定一个n*m的字符矩阵有’.‘和’#‘两种字符，其中’.'为冰块是可移动的到的地方，‘#'为岩石无法移动到该地方。从点(2,2)出发，出发时选择一个方向移动，持续移动至撞上岩石时停止，并重新选择移动方向。问由点(2,2)出发最多可以经过的冰块数量为多少。

问题分析

1.分析移动时前后两个点之间的联系

若前一个点是由停止后，选择新的移动方向进行移动，则后一个点为保持前一个点的移动方向进行移动。若前一个点是移动的，则到后一个点既有可能保持与前一个点同样的移动方向继续移动，也有可能是无法移动从而停止。通过分析两点间的联系，可以发现每个点的状态有2大类，一类为停止，一类为运动，运动里有按运动方向分为上下左右四种。

2.方法1通过BFS将所有按照给定运动方式可以到达的点都标记

因为任意一个点只要有一种运动状态被标记，则该点一定可以由(2,2)点到达，那我们可以让(2,2)为起点跑BFS将所有可以可到达路径上的点都标记，最终统计所有被标记过的点即可得到答案。

代码

#include<bits/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 pair<int, int> PII;
typedef pair<LL, 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;queue<int> q;///将坐标信息和状态映射为一个整数并出入队列中q.push(5*(m+1)+4);while(q.size()){int qt=q.front();q.pop();int x=(qt/5)/m;int y=(qt/5)%m;int d=qt%5;if(d==4){///若当前状态为停止，则选择新的方向移动for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(nx>0&&nx<n-1&&ny>0&&ny<m-1&&g[nx][ny]!='#'&&!st[nx][ny][i]){st[nx][ny][i]=true;q.push(5*(m*nx+ny)+i);}}}else {int nx=x+dx[d],ny=y+dy[d];///若当前运动方向可以接着移动，则继续移动，否则停止，并选择新的方向if(nx>0&&nx<n-1&&ny>0&&ny<m-1&&g[nx][ny]!='#'&&!st[nx][ny][d]){st[nx][ny][d]=true;q.push(5*(m*nx+ny)+d);}else {if(!st[x][y][4]){st[x][y][4]=true;q.push(5*(m*x+y)+4);}}}}
}void solve() {cin >>n >>m;for(int i=0;i<n;i++)    cin >>g[i];bfs();int cnt=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){///若该点有一种状态被标记，则该点可达cnt+=(st[i][j][0]|st[i][j][1]|st[i][j][2]|st[i][j][3]|st[i][j][4]);}}cout <<cnt<<endl;
}  int main() {int t = 1;//cin >> t;while (t--) solve();return 0;
}

3.方法2采用DFS来标记路径上的点的运动状态

代码

停止后再选择新的移动方向可以不用设置为一个单独的状态，而是直接选择新的方向，从而省去停止状态

#include<bits/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 pair<int, int> PII;
typedef pair<LL, 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 nx=x+dx[d],ny=y+dy[d];if(g[nx][ny]!='#'){///可以继续移动dfs(nx,ny,d);}else{//更换方向for(int i=0;i<4;i++){nx=x+dx[i],ny=y+dy[i];dfs(nx,ny,i);}}
}void solve() {cin >>n >>m;for(int i=0;i<n;i++)    cin >>g[i];memset(st,false,sizeof(st));dfs(1,1,3);int cnt=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cnt+=(st[i][j][0]|st[i][j][1]|st[i][j][2]|st[i][j][3]);}}cout <<cnt<<endl;
}  int main() {int t = 1;//cin >> t;while (t--) solve();return 0;
}