列表

详情

NC232334. Invasion of Sjkmost

描述

Sjkmost devotes himself in spreading language virus to the whole SUSTech. Yesterday he found a secret road with length  and width  between the  and the  dormitory (You can refer it as grids), so he decided to invade the  dormitory through it.


At the beginning of the semester, each grid of the road was covered by a brick. However Sjkmost's farsighted teammate FluffyBunny precisely predicted his invasion and removed some of the bricks. Initially Sjkmost is on the side of the  dormitory and would like to move to the other side of the  dormitory. To secretly complete his invasion, Sjkmost can only step on bricks and move to one of the four adjacent bricks (up, down, left, right). He can choose to step on any brick at the  dormitory's side and enter the  dormitory from any brick at the  dormitory's side.


Sjkmost would be thankful if you tell him the minimum number of bricks he must add to complete his invasion, as he wants to save money for his pork elbows.

输入描述

The first line contains two integers N,M.
The next N lines each contain a 01-string with length M. 1 represents a brick, and 0 represents an empty unit.
Note that the first line connects with the  dormitory and the last line connects with the  dormitory.

输出描述

Output a single integer indicating the minimum number of bricks Sjkmost needs to add.

示例1

输入: 

4 4
0000
0000
0000
0000

输出: 

4

说明:

In Sample 1, farsighted FluffyBunny left no bricks for Sjkmost.

示例2

输入: 

7 7
0100100
0000100
1000000
0110010
1100000
0010000
0000100

输出: 

4

说明:


In Sample 2, Sjkmost can add bricks at (2,2), (3,2), (6,2), and (7,3) to make it to the other side.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 117ms, 内存消耗: 8228K, 提交时间: 2021-12-30 19:40:24 

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char s[N][N];
int n,m,ans,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
bool vis[N][N];
struct F{
	int x,y,w;
	bool operator<(const F &S)const {
		return S.w<w;
	}
};
priority_queue<F>q;
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) 
		cin>>s[i]+1;
	for(int i=1; i<=m; i++) {
		vis[1][i]=1;
		if(s[1][i]=='1')  q.push({1,i,0});
		else  q.push({1,i,1});
	}
	while(!q.empty()) {
		auto t=q.top();
		q.pop();
		if(t.x==n) {
			cout<<t.w;
			return 0;
		}
		for(int i=0; i<4; i++) {
			int tx=t.x+dx[i], ty=t.y+dy[i];
			if(tx<1||tx>n||ty<1||ty>m||vis[tx][ty])  continue;
			vis[tx][ty]=1;
			if(s[tx][ty]=='1')  q.push({tx,ty,t.w});
			else  q.push({tx,ty,t.w+1});
		}
	}
}

上一题

© 2024 nowcoder.com